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