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:
 
Source
< Prev   CONTENTS   Source   Next >