sidef-scripts/Math/jacobi_symbol.sf

#!/usr/bin/ruby

# Simple implementation of the Jacobi symbol (a|n).

# See also:
#   https://rosettacode.org/wiki/Jacobi_symbol
#   https://en.wikipedia.org/wiki/Jacobi_symbol
#   https://en.wikipedia.org/wiki/Kronecker_symbol

func jacobi(a, n) {

    assert(n > 0,    "#{n} must be positive")
    assert(n.is_odd, "#{n} must be odd")

    var t = 1
    while (a %= n) {
        if (a.is_even) {
            var v = a.valuation(2)
            t *= (-1)**v if (n%8 ~~ [3,5])
            a >>= v
        }
        (a,n) = (n,a)
        t = -t if ([a%4, n%4] == [3,3])
    }

    n==1 ? t : 0
}

for a in (0..10), n in (0..10) {
    assert_eq(jacobi(a, 2*n + 1), kronecker(a, 2*n + 1))
}