/*
  Author:  Pate Williams (c) 1997

  Algorithm 1.7.3 (Square Test). See "A Course in
  Cpomutational Algebraic Number Theory" by Henri
  Cohen page 40.
*/

#include <ctype.h>
#include <stdio.h>
#include "lip.h"

int square_test(verylong zn, verylong *zq)
{
  int square = 1;
  long q11[11], q63[63], q64[64], q65[65];
  long k, r, t;
  verylong zd = 0;

  for (k = 0; k < 11; k++) q11[k] = 0;
  for (k = 0; k < 6; k++) q11[(k * k) % 11] = 1;
  for (k = 0; k < 63; k++) q63[k] = 0;
  for (k = 0; k < 32; k++) q63[(k * k) % 63] = 1;
  for (k = 0; k < 64; k++) q64[k] = 0;
  for (k = 0; k < 32; k++) q64[(k * k) % 64] = 1;
  for (k = 0; k < 65; k++) q65[k] = 0;
  for (k = 0; k < 33; k++) q65[(k * k) % 65] = 1;
  t = zsmod(zn, 64l);
  r = zsmod(zn, 45045);
  if (q64[t] == 0) square = 0;
  if (square && q63[r % 63] == 0) square = 0;
  if (square && q65[r % 65] == 0) square = 0;
  if (square && q11[r % 11] == 0) square = 0;
  if (square) {
    zsqrt(zn, zq, &zd);
    if (zscompare(zd, 0l) != 0) square = 0;
  }
  zfree(&zd);
  return square;
}

int main(void)
{
  char answer[256];
  verylong zn = 0, zq = 0;

  do {
    printf("enter the number to be tested below:\n");
    zread(&zn);
    if (square_test(zn, &zq)) {
      printf("number is the square of ");
      zwriteln(zq);
    }
    else printf("number is not a square\n");
    printf("another number (n or y)? ");
    scanf("%s", answer);
  } while (tolower(answer[0]) == 'y');
  zfree(&zn);
  zfree(&zq);
  return 0;
}