# Jacobi Symbols

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