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.

Go

The big.Jacobi function in the standard library (for 'big integers') returns the Jacobi symbol for given values of 'a' and 'n'.

This translates the Lua code in the above referenced Wikipedia article to Go (for 8 byte integers) and checks that it gives the same answers for a small table of values - which it does. <lang go>package main

import (

   "fmt"
   "log"
   "math/big"

)

func jacobi(a, n uint64) int {

   if n%2 == 0 {
       log.Fatal("'n' must be a positive odd integer")
   }
   a %= n
   result := 1
   for a != 0 {
       for a%2 == 0 {
           a /= 2
           nn := n % 8
           if nn == 3 || nn == 5 {
               result = -result
           }
       }
       a, n = n, a
       if a%4 == 3 && n%4 == 3 {
           result = -result
       }
       a %= n
   }
   if n == 1 {
       return result
   }
   return 0

}

func main() {

   fmt.Println("Using hand-coded version:")
   fmt.Println("n/a  0  1  2  3  4  5  6  7  8  9")
   fmt.Println("---------------------------------")
   for n := uint64(1); n <= 17; n += 2 {
       fmt.Printf("%2d ", n)
       for a := uint64(0); a <= 9; a++ {
           fmt.Printf(" % d", jacobi(a, n))
       }
       fmt.Println()
   }

   ba, bn := new(big.Int), new(big.Int)
   fmt.Println("\nUsing standard library function:")
   fmt.Println("n/a  0  1  2  3  4  5  6  7  8  9")
   fmt.Println("---------------------------------")
   for n := uint64(1); n <= 17; n += 2 {
       fmt.Printf("%2d ", n)
       for a := uint64(0); a <= 9; a++ {
           ba.SetUint64(a)
           bn.SetUint64(n)
           fmt.Printf(" % d", big.Jacobi(ba, bn))            
       }
       fmt.Println()
   }

}</lang>

Output:

Using hand-coded version:
n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
 1   1  1  1  1  1  1  1  1  1  1
 3   0  1 -1  0  1 -1  0  1 -1  0
 5   0  1 -1 -1  1  0  1 -1 -1  1
 7   0  1  1 -1  1 -1 -1  0  1  1
 9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1

Using standard library function:
n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
 1   1  1  1  1  1  1  1  1  1  1
 3   0  1 -1  0  1 -1  0  1 -1  0
 5   0  1 -1 -1  1  0  1 -1 -1  1
 7   0  1  1 -1  1 -1 -1  0  1  1
 9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1

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>

zkl

<lang zkl>fcn jacobi(a,n){

  if(n.isEven or n<1) 
     throw(Exception.ValueError("'n' must be a positive odd integer"));
  a=a%n;   result,t := 1,0;
  while(a!=0){
     while(a.isEven){

a/=2; n_mod_8:=n%8; if(n_mod_8==3 or n_mod_8==5) result=-result;

     }
     t,a,n = a,n,t;
     if(a%4==3 and n%4==3) result=-result;
     a=a%n;
  }
  if(n==1) result else 0

}</lang> <lang zkl>println("Using hand-coded version:"); println("n/a 0 1 2 3 4 5 6 7 8 9"); println("---------------------------------"); foreach n in ([1..17,2]){

  print("%2d ".fmt(n));
  foreach a in (10){ print(" % d".fmt(jacobi(a,n))) }
  println();

}</lang>

Library: GMP

GNU Multiple Precision Arithmetic Library

<lang zkl>var [const] BI=Import.lib("zklBigNum"); // libGMP println("\nUsing BigInt library function:"); println("n/a 0 1 2 3 4 5 6 7 8 9"); println("---------------------------------"); foreach n in ([1..17,2]){

  print("%2d ".fmt(n));
  foreach a in (10){ print(" % d".fmt(BI(a).jacobi(n))) }
  println();

}</lang>

Output:

Using hand-coded version:
n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
 1   1  1  1  1  1  1  1  1  1  1
 3   0  1 -1  0  1 -1  0  1 -1  0
 5   0  1 -1 -1  1  0  1 -1 -1  1
 7   0  1  1 -1  1 -1 -1  0  1  1
 9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1

Using BigInt library function:
n/a  0  1  2  3  4  5  6  7  8  9
---------------------------------
 1   1  1  1  1  1  1  1  1  1  1
 3   0  1 -1  0  1 -1  0  1 -1  0
 5   0  1 -1 -1  1  0  1 -1 -1  1
 7   0  1  1 -1  1 -1 -1  0  1  1
 9   0  1  1  0  1  1  0  1  1  0
11   0  1 -1  1  1  1 -1 -1 -1  1
13   0  1 -1  1  1 -1 -1 -1 -1  1
15   0  1  1  0  1  0  0 -1  1  0
17   0  1  1 -1  1 -1 -1 -1  1  1