Jacobi Symbol (Python)

From LiteratePrograms

Other implementations: Erlang | Haskell | Python

The Jacobi symbol satisfies the six properties listed below, and these can be used to compute the Jacobi symbol in polynomial time.

1. .

   <<property 1>>=
   def jacobi(a,n):
       if a == 0:
           return 0
   

2. .

   <<property 2>>=
       if a == 1:
           return 1
   

3. .

   <<property 3>>=
       if a == 2:
           n8 = n%8
           if n8 == 3 or n8 == 5:
               return -1
           else:
               return 1
   




4. <<property 4>>=
       if a%2 == 0:
           return jacobi(2,n) * jacobi(a//2,n)
   

5. For ,.

   <<property 5>>=
       if a >= n:
           return jacobi(a%n,n)
   

6. For odd coprimes a and n, .

   <<property 6>>=
       if a%4 == 3 and n%4 == 3:
           return -jacobi(n,a)
       else:
           return jacobi(n,a)
   

From these properties we can come up with a polynomial time algorithm.

<<jacobi symbol>>=
property 1
property 2
property 3
property 4
property 5
property 6

This can be run from the command line

<<jacobi.py>>=
jacobi symbol
if __name__ == '__main__':
    print(jacobi(127,703))
    print(jacobi(11,91))
    print(jacobi(2,7))
    print(jacobi(5,7))
    print(jacobi(14,7))

Download code