3.10 Legendre and Jacobi Symbols – Introduction to Cryptography with Coding Theory, 3rd Edition

3.10 Legendre and Jacobi Symbols

Suppose we want to determine whether or not x2a(modp) has a solution, where p is prime. If p is small, we could square all of the numbers mod p and see if a is on the list. When p is large, this is impractical. If p3(mod4),  we can use the technique of the previous section and compute sa(p+1)/4(modp). If a has a square root, then s is one of them, so we simply have to square s and see if we get a. If not, then a has no square root mod p. The following proposition gives a method for deciding whether a is a square mod p that works for arbitrary odd p.

Proposition

Let p be an odd prime and let a be an integer with a0(modp). Then a(p1)/2±1(modp). The congruence x2a(modp) has a solution if and only if a(p1)/21(modp).

Proof. Let ya(p1)/2(modp). Then y2ap11(modp),  by Fermat’s theorem. Therefore (Exercise 15), y±1(modp).

If ax2,  then a(p1)/2xp11(modp). The hard part is showing the converse. Let α be a primitive root mod p. Then aαj for some j. If a(p1)/21(modp),  then

αj(p1)/2a(p1)/21(modp).

By the Proposition of Section 3.7, j(p1)/20(modp1). This implies that j must be even: j=2k. Therefore, agj(αk)2(modp),  so a is a square mod p.

The criterion is very easy to implement on a computer, but it can be rather difficult to use by hand. In the following, we introduce the Legendre and Jacobi symbols, which give us an easy way to determine whether or not a number is a square mod p. They also are useful in primality testing (see Section 9.3).

Let p be an odd prime and let a0(modp). Define the Legendre symbol

(ap)={ +1ifx2a(modp)hasasolution.1ifx2a(modp)hasnosolution.

Some important properties of the Legendre symbol are given in the following.

Proposition

Let p be an odd prime.

  1. If ab0(modp),  then

    ap=bp.
  2. If a0(modp),  then

    (ap)a(p1)/2(modp).
  3. If ab0(modp),  then

    abp=apbp.
  4. 1p=(1)(p1)/2.

Proof. Part (1) is true because the solutions to X2a are the same as those to X2b when ab(modp).

Part (2) is the definition of the Legendre symbol combined with the previous proposition.

To prove part (3), we use part (2):

(abp)(ab)(p1)/2a(p1)/2b(p1)/2(ap)(bp)(modp).

Since the left and right ends of this congruence are ±1 and they are congruent mod the odd prime p,  they must be equal. This proves (3).

For part (4), use part (2) with a=1:

(1p)(1)(p1)/2(modp).

Again, since the left and right sides of this congruence are ±1 and they are congruent mod the odd prime p,  they must be equal. This proves (4).

Example

Let p=11. The nonzero squares mod 11 are 1, 3, 4, 5, 9. We have

611711=(1)(1)=+1

and (use property (1))

4211=911=+1.

Therefore,

611711=4211.

The Jacobi symbol extends the Legendre symbol from primes p to composite odd integers n. One might be tempted to define the symbol to be +1 if a is a square mod n and 1 if not. However, this would cause the important property (3) to fail. For example, 2 is not a square mod 35, and 3 is not a square mod 35 (since they are not squares mod 5), but also the product 6 is not a square mod 35 (since it is not a square mod 7). If Property (3) held, then we would have (1)(1)=1,  which is false.

In order to preserve property (3), we define the Jacobi symbol as follows. Let n be an odd positive integer and let a be a nonzero integer with gcd(a, n)=1. Let

n=p1b1p2b2prbr

be the prime factorization of n. Then

(an)=(ap1)b1(ap2)b2(apr)br.

The symbols on the right side are the Legendre symbols introduced earlier. Note that if n=p,  the right side is simply one Legendre symbol, so the Jacobi symbol reduces to the Legendre symbol.

Example

Let n=135=335. Then

2135=23325=(1)3(1)=+1.

Note that 2 is not a square mod 5, hence is not a square mod 135. Therefore, the fact that the Jacobi symbol has the value +1 does not imply that 2 is a square mod 135.

The main properties of the Jacobi symbol are given in the following theorem. Parts (1), (2), and (3) can be deduced from those of the Legendre symbol. Parts (4) and (5) are much deeper.

Theorem

Let n be odd.

  1. If ab(modn) and gcd(a, n)=1,  then

    (an)=(bn).
  2. If gcd(ab, n)=1,  then

    (abn)=(an)(bn).
  3. 1n=(1)(n1)/2.

  4. (2n)={ +1ifn1 or 7(mod8)1ifn3 or 5(mod8).
  5. Let m be odd with gcd(m, n)=1. Then

    (mn)={ (nm)ifmn3(mod4)+(nm)otherwise.

Note that we did not include a statement that ana(n1)/2. This is usually not true for composite n (see Exercise 45). In fact, the Solovay-Strassen primality test (see Section 9.3) is based on this fact.

Part (5) is the famous law of quadratic reciprocity, proved by Gauss in 1796. When m and n are primes, it relates the question of whether m is a square mod n to the question of whether n is a square mod m.

A proof of the theorem when m and n are primes can be found in most elementary number theory texts. The extension to composite m and n can be deduced fairly easily from this case. See [Niven et al.], [Rosen], or [KraftW], for example.

When quadratic reciprocity is combined with the other properties of the Jacobi symbol, we obtain a fast way to evaluate the symbol. Here are two examples.

Example

Let’s calculate 456712345:

456712345=+123454567(by(5), since123451   (mod 4))=+32114567(by(1), since123453211   (mod4567))=45673211(by(5))=13563211(by(1))=2321123393211(by(2), since1356=22339)=3393211(since(±1)2=1)=+3211339(by (5))=+160339(by(1))=+233955339(by(2), since160=255)=+(1)55339(by(4))=3395(by(5))=45(by(1))=252=1.

The only factorization needed in the calculation was removing powers of 2, which is easy to do. The fact that the calculations can be done without factoring odd numbers is important in the applications. The fact that the answer is 1 implies that 4567 is not a square mod 12345. However, if the answer had been +1,  we could not have deduced whether 4567 is a square or is not a square mod 12345. See Exercise 44.

Example

Let’s calculate 107137:

107137=+137107(by (5))=+30107(by (1))
=+(2107)(15107)(by (2))=+(1)(15107)(by (4))=+(10715)(by (5))=+(215)(by (1))=+1(by (5)).

Since 137 is a prime, this says that 107 is a square mod 137. In contrast, during the calculation, we used the fact that 215=+1. This does not mean that 2 is a square mod 15. In fact, 2 is not a square mod 5, so it cannot be a square mod 15. Therefore, although we can interpret the final answer as saying that 107 is a square mod the prime 137, we should not interpret intermediate steps involving composite numbers as saying that a number is a square.

Suppose n=pq is the product of two large primes. If an=1,  then we can conclude that a is not a square mod n. What can we conclude if an=+1? Since

(an)=(ap)(aq), 

there are two possibilities:

ap=aq=1orap=aq=+1.

In the first case, a is not a square mod p,  therefore cannot be a square mod pq.

In the second case, a is a square mod p and mod q. The Chinese remainder theorem can be used to combine a square root mod p and a square root mod q to get a square root of a mod n. Therefore, a is a square mod n.

Therefore, if an=+1,  then a can be either a square or a nonsquare mod n. Deciding which case holds is called the quadratic residuosity problem. No fast algorithm is known for solving it. Of course, if we can factor n,  then the problem can easily be solved by computing ap.