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.
 
NB. direct translation of the Lua program found
NB. at the wikipedia entry incorporated here in comments.
 
NB.function jacobi(n, k)
jacobi=: dyad define every
 
  k=. x  NB. k is the left argument
  n=. y  NB. n is the right hand argument
 
NB.assert(k > 0 and k % 2 == 1)
  assert. (k > 0) *. 1 = 2 | k
 
NB.n = n % k
  n =. k | n
 
NB.t = 1
  t =. 1
 
NB.while n ~= 0 do
  while. n do.
 
NB. while n % 2 == 0 do
    while. -. 2 | n do.
 
NB.   n = n / 2
      n =. <. n % 2
 
NB.   r = k % 8
      r =. 8 | k
 
NB.   if r == 3 or r == 5 then
      if. r e. 3 5 do.
 
NB.     t = -t
        t =. -t
 
NB.   end
      end.
 
NB. end
    end.
 
NB. n, k = k, n
    'n k' =. k , n
 
NB. if n % 4 == 3 and k % 4 == 3 then
    if. (3 = 4 | n) *. (3 = 4 | k) do.
 
NB.   t = -t
      t =. -t
 
NB. end
    end.
 
NB. n = n % k
    n =. k | n
 
NB.end
  end.
 
NB.if k == 1 then
  if. k = 1 do.
 
NB. return t
    t
 
NB.else
  else.
 
NB. return 0
    0
 
NB.end
  end.
 
NB.end
)
 