# JacobiSymbol.frink

``` // Calculate the Jacobi Symbol // // This is used in many prime-testing algorithms.  The Jacobi symbol is a // generalization of the Legendre symbol, and this function can be used to // calculate the Legendre symbol as well. // // The Legendre symbol and Jacobi symbol are often written as (n/m) which is // horrible notation that's indistinguishable from a parenthesized division. // // The following implementation is derived from: // // http://primes.utm.edu/glossary/page.php?sort=JacobiSymbol // // which is identical to the algorithm given in _Algorithmic Number Theory, // Vol. 1_ by Eric Bach and Jeffrey Shallit, p. 113. // // However, this algorithm is fixed to work with negative values of a as // outlined in Algorithm 2.3.5 in _Prime Numbers: A Computational Perspective_ // by Richard Crandall and Carl Pomerance. // // This algorithm executes in O(log2[a] log2[n]) time. // // This is the prototype for the implementation of this function inside // Frink, which is faster and does more argument checking. // // The second argument should be a positive odd integer, but this does // not check that condition. JacobiSymbol[a,n] := {    j = 1    a = a mod n    if (a < 0)                   // Fix for the sign convention that this       a = a + n                 // algorithm expects (positive moduli)        while (a != 0)    {       while (a mod 2 == 0)        // a is even       {          a = a / 2          res = n mod 8          if res == 3 or res == 5             j = -j       }       temp = a       a = n       n = temp       if ((a mod 4) ==3) and ((n mod 4) ==3)          j = -j       a = a mod n    }    if (n==1)       return j    else       return 0 }```