 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 € Qp if p = 1 (mod 4), and —1 € Qp if p = 3 (mod 4).
• (ii) (y) = (?) (?)• Hence if « € Z;, then (f) = 1.
• (iii) If a = b (mod p), then (|) = (|).
• (iy) (|) = (—1)(p2-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 ■ ■ • pekk 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”2x)/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 = 2ea 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 = 2ea, 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 € Qn, 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 Ъ* and their Jacobi symbols. Recall from Example 2.138 that Q2r = {L4,16}. Observe that
• (£) = lbut5*Q2r. □
 d € Z-2i i 2 4 5 8 10 11 13 16 17 19 20 a2 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 Z21.

• 2.154 Definition Let n > 3 be an odd integer, and let Jn = {a e Z* | (}}) = 1}. The set of pseudosquares modulo n, denoted Q„, is defined to be the set ./„ - Qn.
• 2.155 Fact Let n = pq be a product of two distinct odd primes. Then Qn = Qn = (p - l)(q - l)/4; that is, half of the elements in Jn 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 aQn. Then a has precisely four square roots modulo n, exactly one of which is also in Qn.
• 2.158 Definition Let n be a Blum integer and let a € Qn- The unique square root of a in Qn 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 / : Qn —> Q„ defined by f(x) = x2 mod 11 is a permutation. The inverse function of / is: 