|
|
|
An efficient algorithm for calculating the Jacobi Symbol starts by applying the following principles:
Jacobi(a,b) = 0, if b is not a positive odd integer.
Jacobi(-a,b) = Jacobi(a,b) if b≡1 (mod 4), and
Jacobi(-a,b) = -Jacobi(a,b) if b≡3 (mod 4).
After that, it works by repeatedly applying the following three principles. First, factors of 2 are removed from the top parameter, so that it becomes odd. Second, the Jacobi symbol is turned upside down. Third, the top parameter is replaced by its value modulo the bottom parameter.
Jacobi(2a,b) = Jacobi(a,b) if b≡�1 (mod 8), and
Jacobi(2a,b) = -Jacobi(a,b) if b≡�3 (mod 8).Jacobi(b,a) = Jacobi(a,b) if a≡1 or b≡1 (mod 4), and
Jacobi(b,a) = -Jacobi(a,b) if a≡3 and b≡3 (mod 4).Jacobi(a Mod b,b) = Jacobi(a,b)
This continues until the Jacobi(0,1) is reached, which is defined as 1, or Jacobi(0,n) is reached for n≠1, which is defined as 0.
Here is the pseudocode:
Jacobi(a,b) {
If (b<=0 Or (b Mod 2)==0) return(0);
j=1;
if (a<0) {
a=-a;
If ((b Mod 4)==3) j=-j;}
Do While (a!=0) {
Do While ((a Mod 2)==0) {
/* Process factors of 2: Jacobi(2,b)=-1 if b=3,5 (mod 8) */
a = a/2
If ((b Mod 8)==3 Or (b Mod 8)==5) j=-j;}
/* Quadratic reciprocity: Jacobi(a,b)=-Jacobi(b,a) if a=3,b=3 (mod 4) */
interchange(a,b);
If ((a Mod 4)==3 And (b Mod 4)==3) j=-j;
a = a Mod b;}
If (b==1) {return(j)}
Else return(0);}
This program uses VBA, and has been well tested. Due to the way VBA handles the "Mod" function (it uses long integers rather than floating point numbers), this implementation avoids using this function, resorting to the "Int" function instead. Also, in this function, we assume the input values, a and b, are integers less than 253, stored as floating point numbers just for the extra size this representation affords. This implementation ensures the input numbers are, in fact, integers.
Function Jacobi(ByVal a As Double, ByVal b As Double) As Double
Dim j As Integer, c As Double, b1 As Double
a = Int(a + 0.25) ' make sure parameters are really integers
b = Int(b + 0.25)
If b <= 0 Or Int(b / 2) * 2 = b Then
Jacobi = 0
Exit Function
End If
j = 1
If a < 0 Then
a = -a
If b - Int(b / 4) * 4 = 3 Then j = -j
End If
Do While a <> 0
Do While Int(a / 2) * 2 = a
' Process factors of 2: Jacobi(2,b)=-1 if b=3,5 (mod 8)
a = a / 2
b1 = b - Int(b / 8) * 8 ' b1 = b Mod 8
If b1 = 3 Or b1 = 5 Then j = -j
Loop
' Quadratic reciprocity: Jacobi(a,b)=-Jacobi(b,a) if a=3,b=3 (mod 4)
c = b: b = a: a = c
If a - Int(a / 4) * 4 = 3 And b - Int(b / 4) * 4 = 3 Then j = -j
a = a - Int(a / b) * b ' a = a Mod b
Loop
If b = 1 Then
Jacobi = j
Else
Jacobi = 0
End If
End Function
Mathworld: Jacobi Symbol
Prime Glossary: Jacobi Symbol shows the computer program that was adapted here (although it doesn't work correctly for Jacobi(a,1)
http://www.math.fau.edu/richman/jacobi.htm contains a good Jacobi Javascript program
. . . . . . fix this program, in particular (a|1) should be 0, even (0|1)=0, and move the "modified date" stuff to its own javascript "how-to" page
Legendre symbol — ( a
p) , where a is any integer, and p is an odd prime
Jacobi symbol — ( a
n) , where a is any integer, and n is a positive integer greater than 2, an extension of the Legendre symbol.
Kronecker symbol — ( a
n) , where a and n are any integers, an extension of the Jacobi symbol.
The webmaster and author of this Math Help site is Graeme McRae.
