cwave.eu5.org Also see: http://www.angelfire.com/dragon/letstry cwave04 at yahoo dot com	My Guestbook Last updated on Fri May 21 11:50:25 IST 2010.
Home > ... tutorials > ... ... Cryptography

Jacobi symbol

Property 0: changing sign of a

• If a = -k then
  1. (a/b) = (k/b) if b=3 (mod 4)
  2. (a/b) = -(k/b) else.

Property 1: simple cases

• If a=1 then (a/b) = 1.
• If a=0 then (a/b) = 0.

Property 2: draining out 4's

• If a=4k then (a/b) = (k/b).

Property 3: halving

• If a=2k then
  1. (a/b) = -(k/b) if b=3,5,11,13 (mod 16)
  2. (a/b) = (k/b) else.

Property 4: remainder

• If a = r (mod b) then (a/b) = (r/b).

Property 5: quadratic reciprocity

• If a is odd then
  1. (a/b) = -(b/a) if a,b=3 (mod 4)
  2. (a/b) = (b/a) else

The algorithm

Implementing in C

#include <stdio.h>


int jacobi(int a, int b) {
  int sgn = 1;
  int tmp, r;


  if(b%2==0) {
    printf("b must be odd.\n");
    return 2;
  }

1



  if(a<0) {
    a = -a;
    if(b%4==3) 
      sgn = 1;
    else
      sgn = -1;
  }

2



  while(1) {





    if(a==1) {
      return sgn;
    }
    else if(a==0) {
      return 0;
    }

3



    else if(a%4==0) {
      a /= 4;
    }

4



    else if(a%2==0) {
      a /= 2;
      r = b%16;
      if(r==3 || r==5 || r==11 || r==13) sgn = -sgn;
    }

5



    else if(a<b) {
      tmp = a;
      a = b;
      b = tmp;
    
      if(a%4==3 && b%4==3) sgn = -sgn;
    }

6



    else {
      a = a%b;
    }

7



  }
}

Explanation of the code:

1:

First we are making sure that b is indeed odd.

2:

If a<0 then we use property 0 to make a positive.

3:

If a=0 or 1 then we can apply property 1.

4:

If a is divisible by 4 then we can divide a by 4.

5:

If a is even then we can use property 3.

6:

If a<b then use quadratic reciprocity.

7:

If a b then use property 4.