22 lines
458 B
Text
22 lines
458 B
Text
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..50), n in (0..50) {
|
|
assert_eq(jacobi(a, 2*n + 1), kronecker(a, 2*n + 1))
|
|
}
|