#include <stdio.h>

#ifdef JACOBI_WARNING
#define WARNING(X) X
#else
#define WARNING(X)
#endif

/***********************************************************************

  Jacobi Symbol

  Implementation: Torsten Sillke, 1991

  --------------------------------------------------------------------
  The Jacobi Symbol is an extension of the Legendre Symbol.
  There are several extension of the Jacobi Symbol named after:
    Kronecker, Hilbert, and Zolotarev.

  Zolotarev's extension of the Jacobi Symbol

  I've gradually come around to a very firm opinion about "the best" 
  definition to use, namely  Zolotarev's, namely:
 
    (a/n)  is the sign of the permutation of multiplying by  a
           on the integers modulo the odd number  n.
 
  (When it isn't a permutation, it's underfined or  0  according
  to taste.)   This definition has the property  (a/n) = (a/-n).
 
     This gives all the properties (including Quadratic Reciprocity)
  very easily.
 
        John Conway
***********************************************************************/

int jacobi_symbol (int d, int n)
{
   int  two, expo_1, n_mod_8, d_mod_4;
   int  help;

   if (n < 0)  n = -n;
   expo_1 = 0;
   n_mod_8 = n & 7;
   
   if (!(n&1))
   {
       WARNING(printf("Jacobi(d,n) with n=%d even. return 0\n",n));
       return 0;
   }
   if (d < 0)
   {
      d = -d;
      if ((n_mod_8&3) == 3)   expo_1 ++;
   }
   
   while (d && n > 1)
   {
      two = 0;
      while (!(d&1))
      {
         two ++;
         d >>= 1;
      }
      if ((two&1)  && (n_mod_8+1 & 4))  expo_1 ++;
      d_mod_4 = d & 3;
      if ((d_mod_4 & n_mod_8) == 3)  expo_1 ++;
      help = n % d;
      n = d;
      d = help;
      n_mod_8 = n & 7;
   }
   
   if ( !d && n-1)
   {
      WARNING(printf("Jacobi(d,n) with gcd > 1. return 0\n"));
      return 0;
   }

   return( (expo_1&1) ? -1 : 1 );
}


main()
{
  int  a,b;
  printf("The Jacobi-Symbol of (d n): ");
  scanf("%d%d", &a, &b); 
  printf("Jacobi(%d,%d) = %d\n", a, b, jacobi_symbol(a,b) );
}