Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Jacobi Symbol Algorithm

Algorithm to calculate Jacobi Symbol

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);}

VBA Program to calculate Jacobi Symbol

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

Internet references

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

Related pages in this website

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.

 

   . . . . . . 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




The webmaster and author of this Math Help site is Graeme McRae.