The Jacobi symbol is just a generalization of the Legendre symbol, \(\Big( \frac{a}{p} \Big)\,,\) where \(a\) is a positive integer and \(p\) is odd (with Legendre symbols \(p\) must be prime). If \(a\) is a multiple of \(p\), then it is \(0\), if \(a\) has a square root \(\mod{p}\) then \(1\), and otherwise \(-1\).

```
function jacobi(a, n)
a %= n
t = 1
while a != 0
while iseven(a)
a = div(a, 2)
((n % 8) in [3, 5]) && (t *= -1)
end
a, n = n, a
(a % 4 == n % 4 == 3) && (t *= -1)
a = a % n
end
return n == 1 ? t : 0
end
```

© Daniel Marvin. Last modified: June 19, 2021.