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, 1 hours, 48 minutes ago.