The Legendre and Jacobi symbols
The Legendre symbol is a useful tool for keeping track of whether or not an integer a is a quadratic residue modulo a prime p.
2.145 Definition Let p be an odd prime and a an integer. The Legendre symbol (|) is defined to be
- 2.146 Fact (properties of Legendre symbol) Let p be an odd prime and a, b e Z. Then the Legendre symbol has the following properties:
- (i) (|) = c/p-^{1})/^{2} (mod p). In particular, Q) = 1 and (-d-) = (- l)^{(p_1}^^{2}. Hence —1 € Q_{p} if p = 1 (mod 4), and —1 € Q_{p} if p = 3 (mod 4).
- (ii) (y) = (?) (?)• ^{Hence} if « € Z;, then (f) = 1.
- (iii) If a = b (mod p), then (|) = (|).
- (i^{y}) (|) = (—1)(p^{2-1})/^{8}. Hence (^) = 1 ifp = 1 or 7 (mod 8), and (|) = -1 ifp = 3 or 5 (mod 8).
- (v) (law of quadratic reciprocity) If q is an odd prime distinct from p, then
In other words, (|) = (|) unless both p and q are congruent to 3 modulo 4, in wliich case (f) = -(f).
The Jacobi symbol is a generalization of the Legendre symbol to integers n which are odd but not necessarily prune.
2.147 Definition Let гг > 3 be odd with prime factorization и = p®^{1}^^{2} ■ ■ • p^{e}k^{k} ■ Then the Jacobi symbol (^) is defined to be
Observe that if n is prime, then the Jacobi symbol is just the Legendre symbol.
- 2.148 Fact (properties of Jacobi symbol) Let m > 3, n > 3 be odd integers, and a.b eZ. Then the Jacobi symbol has the following properties:
- (i) (f) =0,1, or - 1. Moreover, (^) = 0 if and only if gcd(a, n) ф 1.
- (ii) (#) = (h)(1)- ^{Hence if a 6 Z}*>’^{then} (тг) = ^{L}
Ш = (£)(£)■
- (iv) If a = b (mod гг), then (^) = (|).
- (v) Ш = 1-
- (vi) (-d-) = (—l)(^{n 1}^^{2}. Hence (-^) = 1 if гг = 1 (mod 4), and (-d-) = — 1 if n = 3
- (mod 4).
- (vii) (£) = (—l)C”^{2}—^{x})/^{8}. Hence (^) = 1 if n = 1 or 7 (mod 8), and (|) = -1 if n = 3 or 5 (mod 8).
- (viii) (^) = (^)(—l)(^{m-1})(”^{-1})/^{4}. In other words, (^) = (^) unless both m and n are congruent to 3 modulo 4, in which case (^) = - (^).
By properties of the Jacobi symbol it follows that if n is odd and a = 2^{e}a where a is odd, then
This observation yields the following recursive algorithm for computing (^), which does not require the prime factorization of гг.
2.149 Algorithm Jacobi symbol (and Legendre symbol) computation JACOBI(a,n)
INPUT: an odd integer гг > 3, and an integer a, 0 < a < n.
OUTPUT: the Jacobi symbol (£) (and hence the Legendre symbol when n is prime).
- 1. If a = 0 then return(O).
- 2. If a = 1 then return! 1).
- 3. Write a = 2^{e}a, where a is odd.
- 4. If e is even then set s<-l. Otherwise set s-t-1 if n = 1 or 7 (mod 8), or set s<--1
if n = 3 or 5 (mod 8).
- 5. If n = 3 (mod 4) and <ч = 3 (mod 4) then set si--s.
- 6. Set zzi<— n mod ai.
- 7. If ai = 1 then retirm(s); otherwise retum(s ■ JACOBI^,aU).
- 2.150 Fact Algoritlnn 2.149 has a running time of 0((lg гг)^{2}) bit operations.
- 2.151 Remark (finding quadratic non-residues modulo a prime p) Let p denote an odd prime. Even though it is known that half of the elements in Z* are quadratic non-residues modulo p (see Fact 2.135), there is no deterministic polynomial-time algorithm known for finding one. A randomized algorithm for finding a quadratic non-residue is to simply select random integers a € Z* until one is found satisfying (|) = -1. The expected number iterations before a non-residue is found is 2, and hence the procedure takes expected polynomial-time.
- 2.152 Example (Jacobi symbol computation) For a = 158 and n = 235, Algorithm 2.149 computes the Jacobi symbol (|||) as follows:
□
Unlike the Legendre symbol, the Jacobi symbol (|) does not reveal whether or not a is a quadratic residue modulo n. It is indeed true that if a € Q_{n}, then (f) = L However, = 1 does not imply that a e Q„ .
- 2.153 Example (quadratic residues and non-residues) Table 2.6 Usts the elements in Ъ*_{2Х} and their Jacobi symbols. Recall from Example 2.138 that Q_{2}r = {L4,16}. Observe that
- (£) = lbut5*Q_{2}r. □
d € Z-2i |
i |
2 |
4 |
5 |
8 |
10 |
11 |
13 |
16 |
17 |
19 |
20 |
a^{2} mod n |
i |
4 |
16 |
4 |
1 |
16 |
16 |
1 |
4 |
16 |
4 |
1 |
(!) |
i |
-1 |
1 |
-1 |
-1 |
1 |
-1 |
1 |
1 |
-1 |
1 |
-1 |
(!) |
i |
1 |
1 |
-1 |
1 |
-1 |
1 |
-1 |
1 |
-1 |
-1 |
-1 |
m |
i |
-1 |
1 |
1 |
-1 |
-1 |
-1 |
-1 |
1 |
1 |
-1 |
1 |
Table 2.6: Jacobi symbols of elements in Z_{21}.
- 2.154 Definition Let n > 3 be an odd integer, and let J_{n} = {a e Z* | (}}) = 1}. The set of pseudosquares modulo n, denoted Q„, is defined to be the set ./„ - Q_{n}.
- 2.155 Fact Let n = pq be a product of two distinct odd primes. Then Q_{n} = Q_{n} = (p - l)(q - l)/4; that is, half of the elements in J_{n} are quadratic residues and the other half are pseudosquares.
Blum integers
- 2.156 Definition A Blum integer is a composite integer of the form n = pq, where p and q are distinct primes each congruent to 3 modulo 4.
- 2.157 Fact Let n = pq be a Blum integer, and let a € Q_{n}. Then a has precisely four square roots modulo n, exactly one of which is also in Q_{n}.
- 2.158 Definition Let n be a Blum integer and let a € Qn- The unique square root of a in Q_{n} is called the principal square root of a modulo n.
- 2.159 Example (Blum integer) For the Blum integer n = 21, J„ = {1,4,5,16,17,20} and Q„ = {5.17,20}. The four square roots of а = 4 are 2, 5,16, and 19, of which only 16 is also in Q21 . Thus 16 is the principal square root of 4 modulo 21. □
- 2.160 Fact If n = pq is a Blum integer, then the function / : Q_{n} —> Q„ defined by f(x) = x^{2} mod 11 is a permutation. The inverse function of / is: