/*
  Author:  Pate Williams (c) 1997

  Exercise
  "4.12 Write a program to evaluate Jacobi symbols
  using the four properties presented in Section
  4.5. The program should not do any factoring,
  other than dividing out powers of two. Test your
  program by computing the following Jacobi
  symbols:
  (610 / 987), (20964 / 1987), (1234567 / 11111111)."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 160.
*/

#include <stdio.h>

int JACOBI(long a, long n)
{
  int s;
  long a1, b = a, e = 0, m, n1;

  if (a == 0) return 0;
  if (a == 1) return 1;
  while ((b & 1) == 0)
    b >>= 1, e++;
  a1 = b;
  m = n % 8;
  if (!(e & 1)) s = 1;
  else if (m == 1 || m == 7) s = + 1;
  else if (m == 3 || m == 5) s = - 1;
  if (n % 4 == 3 && a1 % 4 == 3) s = - s;
  if (a1 != 1) n1 = n % a1; else n1 = 1;
  return s * JACOBI(n1, a1);
}

int main(void)
{
  long a[3] = {610l, 20964l, 1234567l};
  long n[3] = {987l, 1987l, 11111111l};
  long i;

  for (i = 0; i < 3; i++)
    printf("(%8ld / %8ld) = %+d\n", a[i], n[i],
           JACOBI(a[i], n[i]));
  return 0;
}