# Jacobi Symbol (Python)

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))
```