Jacobi symbol

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

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.

If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).

Task

Calculate the Jacobi symbol (a | n).

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>