Download or view JacobiSymbol.frink in plain text format
// 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
}
Download or view JacobiSymbol.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 19965 days, 23 hours, 43 minutes ago.