The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)*p_2^(k_2)*...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of a ^ ((p-1)/2) (mod p)

 (a | p) ≡   1     if a is a square (mod p)
 (a | p) ≡ -1     if a is not a square (mod p)
 (a | p) ≡   0     if a ≡ 0 
If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).

Task

Calculate the Jacobi symbol (a | n).

Reference

 Wikipedia article on Jacobi symbol.
func jacobi(n, k) {
 
    assert(k > 0,    "#{k} must be positive")
    assert(k.is_odd, "#{k} must be odd")
 
    var t = 1
    while (n %= k) {
        var v = n.valuation(2)
        t *= (-1)**v if (k%8 ~~ [3,5])
        n >>= v
        (n,k) = (k,n)
        t = -t if ([n%4, k%4] == [3,3])
    }
 
    k==1 ? t : 0
}
 
for n in (0..50), k in (0..50) {
    assert_eq(jacobi(n, 2*k + 1), kronecker(n, 2*k + 1))
}