YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer Security Handout #7 Professor M. J. Fischer February 9, 2010

The Legendre and Jacobi Symbols

Let a 0, n Z+. Let QR(a,n) hold if (a,n) = 1 and a is a quadratic residue modulo n. Let QNR(a,n) hold if (a,n) = 1 and a is a quadratic non-residue modulo n (i.e., there is no y Z*n such that a y2 (mod n)).

For a prime p, the structure of quadratic residues can be fairly easily explained. Let g be a primitive root of Z*p. Then every element of Z*p is uniquely expressible as gk for some k {0,,p - 2}.

Theorem 1 Let p be a prime, g a primitive root of p, a gk (mod p). Then a is a quadratic residue iff k is even.

Proof: If k is even, then gk∕2 is easily seen to be a square root of a modulo p.

Conversely, suppose a y2 (mod p). Write y g (mod p). Then gk g2 (mod p). Multiplying both sides by g-k, we have 1 g0 g2-k (mod p). But then ϕ(p)2- k. Since 2ϕ(p) = p - 1, it follows that 2k, as desired. __

The following theorem, due to Euler, is now easily proved:

Theorem 2 (Euler) Let p be an odd prime, and let a 0, (a,p) = 1. Then

Proof: Write a gk (mod p).

If QR(a,p) holds, then a is a quadratic residue modulo p, so k is even by Theorem 1. Write k = 2r for some r. Then a(p-1)2 g2r(p-1)2 (gr)p-1 1 (mod p) by Fermat’s theorem.

If QNR(a,p) holds, then a is a quadratic non-residue modulo p, so k is odd by Theorem 1. Write k = 2r + 1 for some r. Then a(p-1)2 g(2r+1)(p-1)2 gr(p-1)g(p-1)2 g(p-1)2 (mod p). Let b = g(p-1)2. Clearly b2 1 (mod p), so b ≡ ±1 (mod p).1 Since g is a primitive root modulo p and (p - 1)2 < p - 1, b = g(p-1)2 ⁄≡ 1 (mod p). Hence, b ≡-1 (mod p). __ Definition: The Legendre symbol is a function of two integers a and p, written . It is defined for a 0 and p an odd prime as follows:

A multiplicative property of the Legendre symbols follows immediately from Theorem 1.

Observation 3 Let a,b 0, p an odd prime. Then

As an easy corollary of Theorem 2, we have:

Corollary 4 Let a 0 and let p be an odd prime. Then

The Jacobi symbol extends the domain of the Legendre symbol. Definition: The Jacobi symbol is a function of two integers a and n, written , that is defined for all a 0 and all odd positive integers n. Let i=1kpiei be the prime factorization of n. Then

Here denotes the previously-defined Legendre symbol. (Note that by this definition, = 1, and = 0 for odd n 3.)

We have seen that if (a,p) = 1 and p is prime, then the Legendre symbol = 1 iff a is a quadratic residue modulo p. It is not true for the Jacobi symbol that 1 (mod n) implies that a is a quadratic residue modulo n. For example, = 1, but 8 is not a quadratic residue modulo 15. However, the converse does hold:

Observation 5 If ⁄≡ 1 (mod n), then a is not a quadratic residue modulo n.

The usefulness of the Jacobi symbol stems from its ability to be computed efficiently, even without knowning the factorization of either a or n. The algorithm is based on the following theorem, which is stated without proof.

Theorem 6 Let n be an odd positive integer, a,b 0. Then the following identities hold:

1. (Quadratic reciprocity). If a is odd, then

Theorem 6 leads directly to a recursive algorithm for computing :

int jacobi(int a, int n)
/⋆ Precondition: a, n >= 0; n is odd ⋆/
{
int ans;

if (a == 0)
ans = (n==1) ? 1 : 0;
else if (a == 2) {
switch (n%8) {
case 1:
case 7:
ans = 1;
break;
case 3:
case 5:
ans = -1;
break;
}
}
else if ( a >= n )
ans = jacobi(a%n, n);
else if (a%2 == 0)
ans = jacobi(2,n)⋆jacobi(a/2, n);
else
ans = (a%4 == 3 && n%4 == 3) ? -jacobi(n,a) : jacobi(n,a);
return ans;
}