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.
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 2∣k, as desired. __
The following theorem, due to Euler, is now easily proved:
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:
Theorem 6 leads directly to a recursive algorithm for computing :