Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

*Jacobi Symbol*

The **Jacobi symbol**, written J(*a,n*), is a generalization of the Legendre symbol to composite moduli; it is defined for any integer *a* and any odd integer *n.* The function shows up in primality testing. The Jacobi symbol is a function on the set of reduced residues of the divisors of *n* and can be calculated by several formulas [1412]. This is one method:

- Definition 1: J(
*a,n*) is only defined if*n*is odd. - Definition 2: J(0
*,n*) = 0. - Definition 3: If
*n*is prime, then the Jacobi symbol J(*a,n*) = 0 if*n*divides*a*. - Definition 4: If
*n*is prime, then the Jacobi symbol J(*a,n*) = 1 if*a*is a quadratic residue modulo*n.* - Definition 5: If
*n*is prime, then the Jacobi symbol J(*a,n*) = - 1 if*a*is a quadratic nonresidue modulo*n*. - Definition 6: If
*n*is composite, then the Jacobi symbol J(*a,n*) = J(*a,p*_{1}) *...* J(*a,p*), where_{m}*p*..._{1}*p*is the prime factorization of_{m}*n*.

The following algorithm computes the Jacobi symbol recursively:

- Rule 1: J(1,
*n*) = 1 - Rule 2: J(
*a*b,n*) = J(*a,n*)*J(*b,n*) - Rule 3: J(2,
*n*) = 1 if (*n*^{2}- 1)/8 is even, and - 1 otherwise - Rule 4: J(
*a,n*) = J((*a*mod*n*),*n*) - Rule 5: J(
*a,b*_{1}**b*_{2}) = J(*a,b*_{1})*J(*a,b*_{2}) - Rule 6: If the greatest common divisor of
*a*and*b*= 1, and*a*and*b*are odd: - Rule 6a: J(
*a,b*) = J(*b,a*) if (*a*- 1)(*b*- 1)/4 is even - Rule 6b: J(
*a,b*) = - J(*b,a*) if (*a-*1)(*b-*1)/4 is odd

Here is the algorithm in C:

/* This algorithm computes the Jacobi symbol recursively */ int jacobi(int a, int b) { int g; assert(odd(b)); if (a >= b) a %= b; /* by Rule 4 */ if (a == 0) return 0; /* by Definition 2 */ if (a == 1) return 1; /* by Rule 1 */ if (a < 0) if (((b-1)/2 % 2 == 0) return jacobi(-a,b); else return -jacobi(-a,b); if (a % 2 == 0) /* a is even */ if (((b*b - 1)/8) % 2 == 0) return +jacobi(a/2, b) else return -jacobi(a/2, b) /* by Rule 3 and Rule 2 */ g = gcd(a,b); assert(odd(a)); /* this is guaranteed by the (a % 2 == 0) test */ if (g == a) /* a exactly divides b */ return 0; /* by Rules 5 and 4, and Definition 2 */ else if (g != 1) return jacobi(g,b) * jacobi(a/g, b); /* by Rule 2 */ else if (((a-1)*(b-1)/4) % 2 == 0) return +jacobi(b,a); /* by Rule 6a */ else return -jacobi(b,a); /* by Rule 6b */ }

If *n* is known to be prime beforehand, simply compute *a ^{((n-1)/2)}* mod

The Jacobi symbol cannot be used to determine whether *a* is a quadratic residue mod *n* (unless *n* is prime, of course). Note that, if J(*a,n*) = 1 and *n* is composite, it is not necessarily true that *a* is a quadratic residue modulo *n*. For example:

- J(7, 143) = J(7, 11)*J(7, 13) = (- 1)(- 1) = 1

However, there is no integer *x* such that *x ^{2}* ≡ 7 (mod 143).

*Blum Integers*

If *p* and *q* are two primes, and both are congruent to 3 modulo 4, then *n* = *pq* is sometimes called a **Blum integer**. If *n* is a Blum integer, each quadratic residue has exactly four square roots, one of which is also a square; this is the principal square root. For example, the principal square root of 139 mod 437 is 24. The other three square roots are 185, 252, and 413.

*Generators*

If *p* is a prime, and *g* is less than *p*, then *g* is a **generator** mod *p* if

- for each
*b*from 1 to*p*- 1, there exists some*a*where*g*≡ b (mod^{a}*p*).

Another way of saying this is that *g* is **primitive** with respect to *p.*

For example, if *p* = 11, 2 is a generator mod 11:

- 2
^{10}= 1024 ≡ 1 (mod 11) - 2
^{1}= 2 ≡ 2 (mod 11) - 2
^{8}= 256 ≡ 3 (mod 11) - 2
^{2}= 4 ≡ 4 (mod 11) - 2
^{4}= 16 ≡ 5 (mod 11) - 2
^{9}= 512 ≡ 6 (mod 11) - 2
^{7}= 128 ≡ 7 (mod 11) - 2
^{3}= 8 ≡ 8 (mod 11) - 2
^{6}= 64 ≡ 9 (mod 11) - 2
^{5}= 32 ≡ 10 (mod 11)

Every number from 1 to 10 can be expressed as 2a (mod *p*).

For *p* = 11, the generators are 2, 6, 7, and 8. The other numbers are not generators. For example, 3 is not a generator because there is no solution to

- 3
^{a}= 2 (mod 11)

In general, testing whether a given number is a generator is not an easy problem. It is easy, however, if you know the factorization of *p* - 1. Let *q _{1}*,

- g
^{(p- 1)/q}mod*p*

for all values of *q* = *q*_{1}, *q _{2},...*,

If that number equals 1 for some value of *q*, then *g* is not a generator. If that value does not equal 1 for any values of *q*, then *g* is a generator.

For example, let *p* = 11. The prime factors of *p* - 1 = 10 are 2 and 5. To test whether 2 is a generator:

- 2
^{(11- 1)/5}(mod 11) = 4 - 2
^{(11- 1)/2}(mod 11) = 10

Previous | Table of Contents | Next |