Jacobi symbol

Jacobi symbol is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

Factor

The jacobi word already exists in the math.extras vocabulary. See the implementation here.

Python

<lang python>def jacobi(a, n):

   a %= n
   result = 1
   while a != 0:
       while a % 2 == 0:
           a /= 2
           n_mod_8 = n % 8
           if n_mod_8 in (3, 5):
               result = -result
       a, n = n, a
       if a % 4 == 3 and n % 4 == 3:
           result = -result
       a %= n
   if n == 1:
       return result
   else:
       return 0</lang>

Scheme

<lang scheme>(define jacobi (lambda (a n)

 (let ((a-mod-n (modulo a n)))
   (define even (lambda ()

(if (even? a-mod-n) (let ((n-mod-8 (modulo n 8))) (case n-mod-8 ((3 5) (* -1 (jacobi (/ a-mod-n 2) n))) ((1 7) (jacobi (/ a-mod-n 2) n)))) 1)))

   (define flip (lambda ()

(if (and (= (modulo a-mod-n 4) 3) (= (modulo n 4) 3)) -1 1)))

   (if (zero? a-mod-n)

(if (= n 1) 1 0) (* (even) (flip) (jacobi n a-mod-n))))))</lang>