Calculate the Kronecker symbol

Question

Relevant links here and here, but here is the short version:

You have an input of two integers a and b between negative infinity and infinity (though if necessary, I can restrict the range, but the function must still accept negative inputs).

Definition of the Kronecker symbol

You must return the Kronecker symbol (a|b) for inputs a and b where

(a|b) = (a|p_1)^e_1 * (a|p_2)^e_2 * ... * (a|p_n)^e_n

where b = p_1^e_1 * p_2^e_2 * ... * p_n^e_n, and p_i and e_i are the primes and exponents in the prime factorization of b.

For an odd prime p, (a|p)=a^((p-1)/2) (mod p) as defined here.

For b == 2, (n|2)={0 for n even; 1 for n odd, n=+/-1 (mod 8); -1 for n odd, n=+/-3 (mod 8)

For b == -1, (n|-1)={-1 for n<0; 1 for n>0

If a >= b, (a|b) == (z|b) where z == a % b. By this property, and as explained here and here, a is a quadratic residue of b if z is, even though a >= b.

(-1|b) = 1 if b == 0,1,2 (mod 4) and -1 if b == 3 (mod 4). (0|b) is 0 except for (0|1) which is 1, because (a|1) is always 1 and for negative a, (-a|b) == (-1|b) * (a|b).

The output of the Kronecker symbol is always -1, 0 or 1, where the output is 0 if a and b have any common factors. If b is an odd prime, (a|b) == 1 if a is a quadratic residue mod b, and -1 if is it is not a quadratic residue.

Rules

• Your code must be a program or a function.

• The inputs must be in the order a b.

• The output must be either -1, 0 or 1.

• This is code golf, so your code does not have to be efficient, just short.

• No built-ins that directly calculate the Kronecker or the related Jacobi and Legendre symbols. Other built-ins (for prime factorization, for example) are fair game.

Examples

>>> kronecker(1, 5)
1
>>> kronecker(3, 8)
-1
>>> kronecker(15, 22)
1
>>> kronecker(21, 7)
0
>>> kronecker(5, 31)
1
>>> kronecker(31, 5)
1
>>> kronecker(7, 19)
1
>>> kronecker(19, 7)
-1
>>> kronecker(323, 455625)
1
>>> kronecker(0, 12)
0
>>> kronecker(0, 1)
1
>>> kronecker(12, 0)
0
>>> kronecker(1, 0)
1
>>> kronecker(-1, 5)
1
>>> kronecker(1, -5)
1
>>> kronecker(-1, -5)
-1
>>> kronecker(6, 7)
-1
>>> kronecker(-1, -7)
1
>>> kronecker(-6, -7)
-1

This is a complicated function, so please let me know if anything is unclear.

Answer 1

CJam (70 bytes)

{_g\zmf+f{:P2+"W>2*(
z1=
;1
7&4-z[0W0X0]=
P%P+P(2/#P%_1>P*-"N/<W=~}:*}

Online demo (test cases generated with Mathematica).

Dissection

{               e# Anonymous function. Stack: a b
  _g\zmf+       e# Factorise b, with special treatment for negatives
                e# CJam also gives special treatment to 0 and 1
                e# Stack: e.g. a [-1 2 2 5]; or a [-1 1]; or a [0 0]; or a [1 2 2 5]
  f{            e# For each "prime" factor P, find (a|P)
    :P2+        e# Extract code for P from an array formed by splitting a string
    "W>2*(      e#   a -> (a|-1)
z1=             e#   a -> (a|0)
;1              e#   a -> (a|1)
7&4-z[0W0X0]=   e#   a -> (a|2)
P%P+P(2/#P%_1>P*-" e# a -> (a|P) for odd prime P
    N/<W=~      e# Split string and select appropriate element
  }
  :*            e# Multiply the components together
}

I found several ways of evaluating (a|2) for the same character count, and have chosen to use the one with the clearest presentation.

integer array <W= is IMO a quite elegant way of doing fallbacks: if the integer is greater than the length of the array, we select the last element.

Other comments

It's disappointing that for odd prime p the direct Fermat-style (a|p) is so short, because there's a very golfy way of finding (a|n) for positive odd n which I wanted to use. The basis is Zolotarev's lemma:

If p is an odd prime and a is an integer coprime to p then the Legendre symbol (a|p) is the sign of the permutation x -> ax (mod p)

This was strengthened by Frobenius to

If a and b are coprime positive odd integers then the Jacobi symbol (a|b) is the sign of the permutation x -> ax (mod b)

and by Lerch to

If b is a positive odd integer and a is an integer coprime to b then the Jacobi symbol (a|b) is the sign of the permutation x -> ax (mod b)

See Brunyate and Clark, Extending the Zolotarev-Frobenius approach to quadratic reciprocity, The Ramanujan Journal 37.1 (2014): 25-50 for references.

And it can easily be strengthened one step further (although I haven't seen this in the literature) to

If b is a positive odd integer and a is an integer then the Jacobi symbol (a|b) is the Levi-Civita symbol of the map x -> ax (mod b).

Proof: if a is coprime to b then we use Zolotarev-Frobenius-Lerch; otherwise the map is not a permutation, and the Levi-Civita symbol is 0 as desired.

This gives the Jacobi symbol calculation

{_2m*{~>},@ff*\ff%::-:*g}

But the special treatment required for (a|-1) and (a|2) mean that I haven't found a way of calculating the Kronecker symbol which is shorter with this approach: it's shorter to factorise and treat the primes individually.

Answer 2

Python 3, 747 369 335 bytes

As an example answer, only slightly golfed, and to give you an idea of what an answer will look like.

And yes, the prime factorization and run-length-encoding bits are cribbed from Pyth with apologies to isaacg.

from itertools import*
def k(d,r):
 if d<0:a=-d;m=1
 else:a=d;m=0
 if r==1:return 1
 p=1;w=r;n=2;f=[]
 while n*n<=w:
  while w%n<1:w//=n;f+=n,
  n+=1
 if w>1:f+=w,
 z=[[k,len(list(g))]for k,g in groupby(f)]
 for i,j in z:
  if i==2:p*=pow(-1,(a*a-1)//8)
  x=pow(a,(i-1)//2,i)
  if x>1:x-=i
  p*=x**j
 if m:p*=pow(-1,(r-1)//2)
 return p

Answer 3

LabVIEW, 44 Bytes LabVIEW Primitives

Since its symetrical i swapped the inputs if a was bigger than b.

Represents the real formula now

counting like always according to

for true case

Answer 4

Mathematica, 169 175 165 bytes

(1|-1)~k~0=_~k~1=1
_~k~0=0
a_~k~-1=If[a<0,-1,1]
a_~k~2=DirichletCharacter[8,2,a]
a_~k~p_/;PrimeQ@p=Mod[a^((p-1)/2),p,-1]
a_~k~b_:=1##&@@(a~k~#^#2&@@@FactorInteger@b)

Answer 5

Julia, 195 bytes

k(a,b)=b==0?a∈[1,-1]?1:0:b==1?1:b==2?iseven(a)?0:a%8∈[1,-1]?1:-1:b==-1?a<1?-1:1:isprime(b)&&b>2?a%b==0?0:a∈[i^2%b for i=0:b-1]?1:-1:k(a,sign(b))*prod(i->k(a,i)^factor(b)[i],keys(factor(b)))

This is a recursive function k that accepts two integers and returns an integer.

Ungolfed:

function k(a::Integer, b::Integer)
    if b == 0
        return a ∈ [1, -1] ? 1 : 0
    elseif b == 1
        return 1
    elseif b == 2
        return iseven(a) ? 0 : a % 8 ∈ [1, -1] ? 1 : -1
    elseif b == -1
        return a < 1 ? -1 : 1
    elseif isprime(b) && b > 2
        return a % b == 0 ? 0 : a ∈ [i^2 % b for i = 1:b-1] ? 1 : -1
    else
        p = factor(b)
        return k(a, sign(b)) * prod(i -> k(a, i)^p[i], keys(p))
    end
end

Answer 6

Haskell, 286 bytes

a#0|abs a==1=1|1<2=0
a#1=1
a#2|even a=0|mod a 8`elem`[1,7]=1|1<2=(-1)
a#b|b<0=a`div`abs a*a#(-b)|all((/=0).mod b)[2..b-1]=if elem n[0,1] then n else(-1)|1<2=product$map(a#)$f b where n=a^(div(b-1)2)`mod`b
f 1=[]
f n|n<0=(-1):f(-n)|1<2=let p=head$filter((==0).mod n)[2..n]in p:f(div n p)

Probably not completely optimized, but a valiant effort. The Kronecker symbol is defined as the infix function a#b, i.e.

*Main>323#455265 
1