Solving quadratic congruences with odd prime moduli

The goal of this post is to show how to solve the quadratic congruence equation

    x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where p is an odd prime and a is an integer that is relatively prime to p. When equation (1) has a solution, the number a is said to be a quadratic residue modulo p. Any solution of equation (1) is called a square root of a modulo p. When the equation has no solutions, the number a is said to be a quadratic nonresidue modulo p. For both theoretical and practical reasons, it is important to solve quadratic congruence equation (1) (or to find square roots modulo an odd prime). This post expands on the previous post called Solving Quadratic Congruences.

____________________________________________________________________________

Background

If the modulus p is small (prime or composite), then it is easy to solve equation (1). Simply square each element in the set \left\{1,2,\cdots,p-1 \right\} modulo p and look for the value a. We need a systematic method only when the modulus is large to the point that checking for solutions by squaring one number at a time cannot be done in a reasonable amount of time using modern supercomputers.

The moduli discussed here are prime numbers p. The case p=2 is easy to deal with. Thus in solving equations described in (1), the focus is on odd primes p and on integers a that are relatively prime to p.

In solving the quadratic congruence equation (1), for that matter any other type of equations, three natural questions arise: given an equation of the form in (1), how do I know if it has a solution? If it has a solution, how many solution does it have? How do I compute a solution of one exists? It turns out that for quadratic congruence equations with odd prime moduli as described in (1), there are clear and definite answers for all three questions.

There is an effective algorithm for checking whether a is a quadratic residue modulo p. The algorithm is to evaluate the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr) (see these two previous posts: Legendre symbol and Jacobi symbol). As for the second question (the number of solutions), the equation (1) either has no solutions or has exactly two solutions (see the post called Solving Quadratic Congruences). Thus for an odd prime p, exactly half of the elements in the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\} are quadratic residues modulo p. In other words, modulo an odd prime p, there are (p-1)/2 many quadratic residues and (p-1)/2 many quadratic nonresidues. To answer the third question, we discuss algorithms that can be used to solve quadratic congruences with odd prime moduli.

Any odd prime is congruent to either 1 or 3 modulo 4. For odd prime p \equiv 3 \ (\text{mod} \ 4), there is an explicit formula that gives the solutions to equation (1). For odd prime p \equiv 1 \ (\text{mod} \ 4), no explicit formula exists. For the case of p \equiv 1 \ (\text{mod} \ 4), we demonstrate how to use the Tonelli-Shanks algorithm to iteratively find the solutions. We describe the algorithm and show how it works with some examples. We also present a proof of why the algorithm works.

The Tonelli-Shanks algorithm was invented in 1972 by Dan Shanks. He called it RESSOL (RESidues SOLver). The algorithm is very similar to one described much earlier by Tonelli, hence the name Tonelli-Shanks algorithm.

____________________________________________________________________________

Odd primes congruent to 3 modulo 4

Let’s take care of the easy case first, i.e. p \equiv 3 \ (\text{mod} \ 4). In this case, the solutions to equation (1) are given by \pm R where

    \displaystyle R \equiv a^{\frac{p+1}{4}} \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

To see that the R gives a solution to the equation (1), consider the following derivation:

    \displaystyle \begin{aligned} R^2&\equiv (a^{\frac{p+1}{4}})^2 \\&\equiv a^{\frac{p+1}{2}} \\&\equiv a \cdot a^{\frac{p-1}{2}} \\&\equiv a \cdot \biggl(\frac{a}{p}\biggr) \\&\equiv a \cdot 1  \\&\equiv a \ (\text{mod} \ p) \end{aligned}

On the surface, it appears that the above derivation works for all primes. Note that the exponent (p+1)/4 must be an integer. The assumption p \equiv 3 \ (\text{mod} \ 4) makes it an integer. Using Euler’s Criterion, the quantity \displaystyle a^{\frac{p-1}{2}} is replaced by the Lengendre symbol, which is a 1 since a is a quadratic residue modulo p.

As a quick example, let’s solve the equation x^2 \equiv 19 \ (\text{mod} \ 431). The prime 431 is congruent to 3 modulo 4. The number 19 is a quadratic residue modulo 431. One solution is given by 19^{432/4} \equiv 19^{108} \equiv 197 \ (\text{mod} \ 431). The other solution is given by 234 (= 431-197).

____________________________________________________________________________

Odd primes congruent to 1 modulo 4

The focus of the remainder of the post is on using the Tonelli-Shanks algorithm to solve the quadratic equation (1). We describe the algorithm in the next section and demonstrate with examples. To follow along the algorithm and the examples, it would be helpful to have a calculator (or a software package) that can handle modular exponentiation and the evaluation of Legendre symbol and Jacobi symbol. The algorithm also requires the finding of a quadratic nonresidue modulo the odd prime p. Obviously, we need to check that the number a is a quadratic residue modulo p. This can be done by evaluating the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr).

____________________________________________________________________________

Tonelli-Shanks Algorithm

Objective: to solve the equation x^2 \equiv a \ (\text{mod} \ p) where p is an odd prime satisfying p \equiv 1 \ (\text{mod} \ 4) and a is a quadratic residue modulo p, i.e. the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr)=1.

Steps:

  1. Factor out the largest power of 2 from the even integer p-1, i.e. obtain p-1=2^{S} \cdot Q where Q is odd.
  2. Find a positive integer y that is a quadratic nonresidue modulo p, i.e. find y such that \displaystyle  \biggl(\frac{y}{p}\biggr)=-1.
  3. Calculate the following four quantities:
    • \displaystyle R \equiv a^{\frac{Q+1}{2}} \ (\text{mod} \ p)
    • \displaystyle c \equiv y^Q \ (\text{mod} \ p)
    • \displaystyle t \equiv a^{Q} \ (\text{mod} \ p)
    • \displaystyle E=S
  4. Loop
    1. If \displaystyle t \equiv 1 \ (\text{mod} \ p), then the algorithm stops and output R and p-R, the two solutions of the equation. If \displaystyle t \not \equiv 1 \ (\text{mod} \ p), then perform the following two steps.
    2. Find the least i such that 0<i<E and such that \displaystyle t^{2^i} \equiv 1 \ (\text{mod} \ p).
    3. Calculate \displaystyle b \equiv c^{2^{E-i-1}} \ (\text{mod} \ p) and replace the quantities R, c, t and E as follows:
      • \displaystyle R \equiv Rb \ (\text{mod} \ p)
      • \displaystyle c \equiv b^2 \ (\text{mod} \ p)
      • \displaystyle t \equiv b^2 \cdot t \ (\text{mod} \ p)
      • \displaystyle E=i

      Go back to Step A.

The initial value of \displaystyle R \equiv a^{\frac{Q+1}{2}} is an initial estimate of the solution to the equation. The rest of the algorithm is to repeatedly refine this estimate to reach a solution. Note that Step 4-B is to determine the order of the number t. Each time a new value of t is calculated, the order of the new t is smaller than the order of the previous t. The goal is to reach a t of order 1, which means that the number t itself would be \equiv 1, at which point the estimate R becomes a solution. Let’s consider some examples.

____________________________________________________________________________

Examples

Example 1
Solve the equation x^2 \equiv 381 \ (\text{mod} \ 593).

The following shows the steps in carrying out the Tonelli-Shanks algorithm.

Step 1. S=4 and Q=37 since 592 = 16 x 37.

Step 2. y=3 is a quadratic nonresidue modulo 593.

Step 3. Calculate the following four quantities:

  • \displaystyle R \equiv 381^{\frac{37+1}{2}} \equiv 381^{19} \equiv 218 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 3^{37} \equiv 384 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 381^{37} \equiv 201 \ (\text{mod} \ 593)
  • \displaystyle E=4

_______________________________________
The above t is obviously t \not \equiv 1. We now find the least i, 0<i<E, such that t^{2^i} \equiv 1. In other words, repeatedly square t until reaching the value of 1. The result is i=3. Let b \equiv c^{2^{E-i-1}} \equiv 384^{2^{4-3-1}} \equiv 384 \ (\text{mod} \ 593). Replace the quantities R, c, t and E as follows:

  • \displaystyle R \equiv 218 \cdot 384 \equiv 99 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 384^{2} \equiv 392 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 201 \cdot 392 \equiv 516 \ (\text{mod} \ 593)
  • \displaystyle E=3

_______________________________________
The last t is obviously t \not \equiv 1. We now find the least i, 0<i<E, such that t^{2^i} \equiv 1. The result is i=2. Note that the order of t goes from 2^3 previously to 2^2.

Let b \equiv c^{2^{E-i-1}} \equiv 392^{2^{3-2-1}} \equiv 392 \ (\text{mod} \ 593). Replace the quantities R, c, t and E as follows:

  • \displaystyle R \equiv 99 \cdot 392 \equiv 263 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 392^{2} \equiv 77 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 516 \cdot 77 \equiv 1 \ (\text{mod} \ 593)
  • \displaystyle E=2

Now we reach t \equiv 1. The solutions to the equations are: 263 and 330 (=593 – 263). \square

Example 2
Solve the equation x^2 \equiv a \ (\text{mod} \ p) where p= 2795830049 and a= 2262876953.

The number p is a prime and the value of the Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr)=1. The following shows the steps.

Step 1. S=5 and Q= 87369689.

Step 2. y=3 is a quadratic nonresidue modulo p. This is the result of a search starting with 2.

Step 3. Calculate the following four quantities. All calculations are modulo p.

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \equiv 2075434035
  • \displaystyle c \equiv 3^{Q} \equiv 268289123
  • \displaystyle t \equiv a^{Q} \equiv 2666735226
  • \displaystyle E=5

The above t is obviously not 1. So we need to perform the loop several times.

_______________________________________
Iteration 1

  • i=4, the least i such that t^{2^i} \equiv 1.
  • b \equiv c^{2^{E-i-1}} \equiv c^{2^{5-4-1}} \equiv c \equiv 268289123
  • \displaystyle R_1 \equiv R \cdot b \equiv 2438491248
  • \displaystyle c_1 \equiv b^2 \equiv 717416975
  • \displaystyle t_1 \equiv c_1 \cdot t \equiv 2569006270
  • \displaystyle E_1=4

_______________________________________
Iteration 2

  • i=2, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_1^{2^{E_1-i-1}} \equiv c_1^{2^{4-2-1}} \equiv c_1^2 \equiv 17652213
  • \displaystyle R_2 \equiv R_1 \cdot b \equiv 2519954933
  • \displaystyle c_2 \equiv b^2 \equiv 2569006270
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \equiv 2795830048
  • \displaystyle E_2=2

_______________________________________
Iteration 3

  • i=1, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_2^{2^{E_2-i-1}} \equiv c_2^{2^{2-1-1}} \equiv c_2 \equiv 2569006270
  • \displaystyle R_3 \equiv R_2 \cdot b \equiv  1147516973
  • \displaystyle c_3 \equiv b^2 \equiv 2795830048
  • \displaystyle t_3 \equiv c_3 \cdot t_2 \equiv 1
  • \displaystyle E_3=1

_______________________________________
Solutions

  • \displaystyle R \equiv 1147516973
  • \displaystyle p-R \equiv 1648313076

____________________________________________________________________________

Why the algorithm works

To prove that the algorithm produces the solutions to the given equation, we need the following lemma.

Lemma
Suppose that both g and h are relatively prime to an odd prime number p. Suppose that the order of g modulo p is 2^j with j being a positive integer. Suppose that the order of h modulo p is also 2^j. Then the order of g \cdot h modulo p is 2^k where k<j.

Proof
Since the order of g is 2^j, \displaystyle y=g^{2^{j-1}} \not \equiv 1 \ (\text{mod} \ p). Note that \displaystyle y^2 \equiv g^{2^{j}} \equiv 1 \ (\text{mod} \ p). Then it must be that y \equiv -1 \ (\text{mod} \ p) since the equation x^2 \equiv 1 \ (\text{mod} \ p) has only two solutions. By a similar argument, h^{2^{j-1}} \equiv -1 \ (\text{mod} \ p). Consider the following:

    \displaystyle (gh)^{2^{j-1}} \equiv g^{2^{j-1}} \cdot h^{2^{j-1}} \equiv (-1) (-1) \equiv 1 \ (\text{mod} \ p)

This means that the order of g \cdot h divides 2^{j-1}. Thus the order of g \cdot h modulo p must be 2^{k} for some k \le j-1 < j. \square

Proof of Tonelli-Shanks algorithm
Since p is an odd prime, we set p-1=Q \cdot 2^{S} where Q is odd. We also select a positive integer y that is a quadratic nonresidue modulo p. To start the calculation, obtain the following four quantities:

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \ (\text{mod} \ p)
  • \displaystyle c \equiv y^Q \ (\text{mod} \ p)
  • \displaystyle t \equiv a^{Q} \ (\text{mod} \ p)
  • \displaystyle E=S

The quantity R is an initial estimate of the desired solution since

    \displaystyle R^2 \equiv a^{Q+1} \equiv a \cdot a^Q \equiv a \cdot t \ (\text{mod} \ p)

If t \equiv 1 \ (\text{mod} \ p), then R would be a solution and the algorithm stops. So assume that t \not \equiv 1 \ (\text{mod} \ p). Then we begin a loop to fine tune R until reaching a step with t \equiv 1 \ (\text{mod} \ p).

To make sense of the loop in the algorithm, consider the quantity c and the quantity t. First of all, the integer c has order 2^S modulo p, as shown below.

    \displaystyle c^{2^S} \equiv (y^{Q})^{2^S} \equiv y^{p-1} \equiv (y^{\frac{p-1}{2}})^2 \equiv (-1)^2 \equiv 1 \ (\text{mod} \ p)

    \displaystyle c^{2^{S-1}} \equiv (y^{Q})^{2^{S-1}} \equiv y^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)

Furthermore, the order of t modulo p is less or equal to 2^S since \displaystyle t^{2^S} \equiv 1 \ (\text{mod} \ p) as shown below.

    \displaystyle t^{2^S} \equiv (a^{Q})^{2^S} \equiv a^{p-1} \equiv (a^{\frac{p-1}{2}})^2 \equiv (1)^2 \equiv 1 \ (\text{mod} \ p)

Let 2^{S_1} be the order of t where S_1 \le S. Now begin the calculation for the first iteration of the loop. First, calculate \displaystyle b_1 \equiv c^{2^{E-S_1-1}} \ (\text{mod} \ p).

  • \displaystyle R_1 \equiv R \cdot b_1 \ (\text{mod} \ p)
  • \displaystyle c_1 \equiv b_1^2 \ (\text{mod} \ p)
  • \displaystyle t_1 \equiv c_1 \cdot t \ (\text{mod} \ p)
  • \displaystyle E_1=S_1

One important point to make is that the order of c_1 modulo p is the same as the order of t, which is 2^{S_1}. The following shows why.

    \displaystyle c_1^{2^{S_1}} \equiv (b_1^2)^{2^{S_1}} \equiv b_1^{2^{S_1+1}} \equiv (c^{2^{E-S_1-1}})^{2^{S_1+1}} \equiv c^{2^S} \equiv 1 \ (\text{mod} \ p)

    \displaystyle c_1^{2^{S_1-1}} \equiv (b_1^2)^{2^{S_1-1}} \equiv b_1^{2^{S_1}} \equiv (c^{2^{E-S_1-1}})^{2^{S_1}} \equiv c^{2^{S-1}} \equiv -1 \ (\text{mod} \ p)

By the lemma, the order of \displaystyle t_1 \equiv c_1 \cdot t \ (\text{mod} \ p) is 2^{S_2} for some S_2<S_1. Note that

    \displaystyle R_1^2 \equiv R^2 \cdot b_1^2 \equiv a \cdot t \cdot c_1 \equiv a \cdot t_1 \ (\text{mod} \ p)

In light of the above, if \displaystyle t_1 \equiv 1 \ (\text{mod} \ p), then R_1 is a solution and the algorithm stops. Even if \displaystyle t_1 \not \equiv 1 \ (\text{mod} \ p), there is progress since the order of t_1 is less than the previous t with 2^{S_2}<2^{S_1}. Repeat the loop to obtain t_2, \cdots, t_k with the order of t_k being 2^{S_{k+1}}=1 where S_{k+1}=0. When the order of t_k is 1, t_k=1. When the modulus is a prime, there is only one element with order 1, namely the element 1. Then the quantity R_j is a solution to the given equation.

To further illustrate, we perform one more iteration of the loop. Let \displaystyle b_2 \equiv c_1^{2^{E_1-S_2-1}} \ (\text{mod} \ p). Calculate the following four quantities:

  • \displaystyle R_2 \equiv R_1 \cdot b_2 \ (\text{mod} \ p)
  • \displaystyle c_2 \equiv b_2^2 \ (\text{mod} \ p)
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \ (\text{mod} \ p)
  • \displaystyle E_2=S_2

Similar to the previous step, the order of c_2 is the same as the order of t_1 as shown below:

    \displaystyle C_2^{2^{S_2}} \equiv (b_2^2)^{2^{S_2}} \equiv b_2^{2^{S_2+1}} \equiv (c_1^{2^{E_1-S_2-1}})^{2^{S_2+1}} \equiv c_1^{2^{E_1}} \equiv c_1^{2^{S_1}} \equiv 1 \ (\text{mod} \ p)

    \displaystyle C_2^{2^{S_2-1}} \equiv (b_2^2)^{2^{S_2-1}} \equiv b_2^{2^{S_2}} \equiv (c_1^{2^{E_1-S_2-1}})^{2^{S_2}} \equiv c_1^{2^{E_1-1}} \equiv c_1^{2^{S_1-1}} \equiv -1 \ (\text{mod} \ p)

By the lemma, the order of \displaystyle t_2 \equiv c_2 \cdot t_1 \ (\text{mod} \ p) is 2^{S_3} for some S_3<S_2. Note the following:

    \displaystyle R_2^2 \equiv R_1^2 \cdot b_2^2 \equiv a \cdot t_1 \cdot c_2 \equiv a \cdot t_2 \ (\text{mod} \ p)

Now we reach the same decision point. If t_2 \equiv 1, then R_2 is a solution and the algorithm stops. Even if t_2 \not \equiv 1, the order of t_2 is smaller than previously. Continue to execute the loop until the step where the order of t_k is 1. \square

____________________________________________________________________________

Comments

The Tonelli-Shanks algorithm works correctly (as the proof indicated) and works efficiently (as the examples show). The speed of the algorithm is a function of the inputs. The inputs to the Tonelli-Shanks algorithm are the odd prime p and the quadratic residue a modulo p. The two inputs are translated to the three quantities m, k and S where m is the number of digits in the binary representation of the odd prime p, k is the number of ones in the binary representation of p and S is the largest power of 2 in the factor of p-1. These three numbers determine the amount of calculations. According to this source, the average number of modular multiplications required by the Tonelli-Shanks algorithm is:

    \displaystyle 2m+2k+\frac{S(S-1)}{4}+\frac{1}{2^{S-1}}-9

Another consideration is the selection of y, a quadratic nonresidue modulo p, which can be found by checking random selections from the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\}. Since half the elements in the set are quadratic residues, it takes on average two random selections from this set (hence two computations of the Legendre symbol). One way to see this is that the number of Bernoulli trials until the first success has a geometric distribution. The probability of success in each trial is 0.5. Then the mean of the geometric distribution is 1/0.5 = 2.

Overall, the Tonelli-Shanks algorithm works efficiently in solving the quadratic congruence equation (1). Along with the explicit formula (2) that handles the case of odd prime congruent to 3 modulo 4, the quadratic congruence equations are completely and efficiently solved. As a result, it is not possible to hide secrets using quadratic congruence equations with odd prime moduli. If a message is embedded as a solution of such equation, then it can be easily recovered using the Tonelli-Shanks algorithm or the explicit formula (2). On the other hand, the equation

    x^2 \equiv a \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

is difficult to solve where the modulus n is the product of two large primes p and q. In fact the Rabin cryptosystem is based on the difficulty of solving equation (3). However, if the factoring of n is known, equation (3) is solvable and the Tonelli-Shanks algorithm along with the Chinese remainder theorem play a crucial role.

____________________________________________________________________________

Another example

Example 3
This is a slightly larger example than the ones given earlier. Solve the equation x^2 \equiv a \ (\text{mod} \ p) where p= 3825123056546413057 and a= 1347234680313589343.

The number p is a prime and the value of the Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr)=1. The following shows the steps.

Step 1. S=9 and Q= 7470943469817213.

Step 2. y=5 is a quadratic nonresidue modulo p. This is the result of a search starting with 2.

Step 3. Calculate the following four quantities. All calculations are modulo p.

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \equiv 2098778229504385555
  • \displaystyle c \equiv 5^{Q} \equiv 945046778698092498
  • \displaystyle t \equiv a^{Q} \equiv 3356211917617579979
  • \displaystyle E=9

The above t is obviously not 1. So we need to perform the loops several times.

_______________________________________
Iteration 1

  • i=8, the least i such that t^{2^i} \equiv 1.
  • b \equiv c^{2^{E-i-1}} \equiv c^{2^{9-8-1}} \equiv c \equiv 945046778698092498
  • \displaystyle R_1 \equiv R \cdot b \equiv 852974818860733646
  • \displaystyle c_1 \equiv b^2 \equiv 777225398785777536
  • \displaystyle t_1 \equiv c_1 \cdot t \equiv 3130593564544117824
  • \displaystyle E_1=8

_______________________________________
Iteration 2

  • i=7, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_1^{2^{E_1-i-1}} \equiv c_1^{2^{8-7-1}} \equiv c_1 \equiv 777225398785777536
  • \displaystyle R_2 \equiv R_1 \cdot b \equiv 1437578878907258220
  • \displaystyle c_2 \equiv b^2 \equiv 872612747799733789
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \equiv 3053369905528253481
  • \displaystyle E_2=7

_______________________________________
Iteration 3

  • i=2, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_2^{2^{E_2-i-1}} \equiv c_2^{2^{7-2-1}} \equiv c_2^{2^5} \equiv 2409792470045159888
  • \displaystyle R_3 \equiv R_2 \cdot b \equiv 1136125891705727966
  • \displaystyle c_3 \equiv b^2 \equiv 3053369905528253481
  • \displaystyle t_3 \equiv c_3 \cdot t_2 \equiv 3825123056546413056
  • \displaystyle E_3=2

_______________________________________
Iteration 4

  • i=1, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_3^{2^{E_3-i-1}} \equiv c_3^{2^{2-1-1}} \equiv c_3^{2^0} \equiv c_3 \equiv 3053369905528253481
  • \displaystyle R_4 \equiv R_3 \cdot b \equiv  3727993796269536942
  • \displaystyle c_4 \equiv b^2 \equiv 3825123056546413056
  • \displaystyle t_4 \equiv c_4 \cdot t_3 \equiv 1
  • \displaystyle E_4=1

_______________________________________
Solutions

  • \displaystyle R \equiv 3727993796269536942
  • \displaystyle p-R \equiv 97129260276876115

____________________________________________________________________________

Exercises

We close with some exercises. Use Tonelli-Shanks algorithm to solve the equation x^2 \equiv a \ (\text{mod} \ p) for each of the following choices of a and p.

  1. p=193 and a = 67
  2. p=569 and a = 367
  3. p=34369 and a = 19170
  4. p=50753 and a = 12957
  5. p=97241 and a = 47861
  6. p=2773676993 and a = 1342865413

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Solutions are:

  1. 35 and 158
  2. 103 and 466
  3. 19136 and 15233
  4. 30781 and 19972
  5. 45733 and 51508
  6. 1056882643 and 1716794350

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

Advertisements

The Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol. In this post, we define the Jacobi symbol and discuss some of its important properties. The Legendre symbol (coupled with the law of reciprocity) is a useful tool in determining whether a number is a quadratic residue modulo an odd prime. However, the Legendre symbol is also restrictive since the bottom argument must be a prime. The Jacobi symbol generalizes the Legendre symbol and in many cases is easier to evaluate than the Legendre symbol. This is demonstrated in several examples.

____________________________________________________________________________

Defining The Jacobi Symbol

The Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr) where the bottom argument is always an odd prime and the top argument can be any integer. When a is an integer that is relatively prime to the odd prime p, the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr) carries information on whether the integer a is quadratic residue modulo p. The following gives the definition of the Legendre symbol.

    \displaystyle  \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl}           0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\           1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic residue modulo }p\\          -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic nonresidue modulo }p \end{array} \right.

The Jacobi symbol \displaystyle  \biggl(\frac{a}{n}\biggr) has the same look as the Legendre symbol. The top argument can be any integer. The bottom argument is an odd positive integer. If the odd positive integer n>1 has the prime factorization n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t}, the Jacobi symbol is defined as follows:

    \displaystyle  \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{p_1}\biggr)^{e_1} \times \biggl(\frac{a}{p_2}\biggr)^{e_2} \times \cdots \times \biggl(\frac{a}{p_t}\biggr)^{e_t}

For convenience, we define \displaystyle  \biggl(\frac{a}{1}\biggr)=1. A slightly different, but equivalent, definition is that whenever the odd integer n>1 has the prime factorization n=q_1 \times q_2 \times \cdots \times q_k (the prime numbers q_j are not necessarily distinct), the symbol \displaystyle  \biggl(\frac{a}{n}\biggr) is defined as follows:

    \displaystyle  \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{q_1}\biggr) \times \biggl(\frac{a}{q_2}\biggr) \times \cdots \times \biggl(\frac{a}{q_k}\biggr)

The Jacobi symbol is defined using the Legendre symbol according to the prime factorization of the bottom argument.

____________________________________________________________________________

Properties of The Jacobi Symbol

Now that the Jacobi symbol has been defined based on the Legendre symbol, there are two natural questions.

  • Does the value of \displaystyle  \biggl(\frac{a}{n}\biggr)= \pm 1 indicates that a is a quadratic residue or nonresidue modulo n?
  • The Legendre symbol follows a set of rules (e.g. the law of quadratic reciprocity) that make the Legendre symbol a versatile tool. Does the Jacobi symbol follow these rules? Conceptually, evaluating the Jacobi symbol requires factoring the bottom argument of the symbol. On the surface, this appears to be a limitation. However, if the Jacobi symbol follows the rules for the Legendre symbol including the law of quadratic reciprocity, it will be just as easy to evaluate the Jacobi symbol.

For the first question, the following is true: If a is a quadratic residue modulo n, then \displaystyle  \biggl(\frac{a}{n}\biggr)=1. The contrapositive of this statement is that if \displaystyle  \biggl(\frac{a}{n}\biggr)=-1, then the number a is a quadratic nonresidue modulo the odd integer n, i.e. the equation x^2 \equiv a \ (\text{mod} \ n) has no solutions. However, the value of \displaystyle  \biggl(\frac{a}{n}\biggr)=1 does not imply that a is a quadratic residue modulo n. For example, \displaystyle  \biggl(\frac{2}{15}\biggr)=1 but the equation x^2 \equiv 2 \ (\text{mod} \ 15) has no solutions. Note that both equations x^2 \equiv 2 \ (\text{mod} \ 3) and x^2 \equiv 2 \ (\text{mod} \ 5) have no solutions. This means that the value of \displaystyle  \biggl(\frac{2}{15}\biggr)=1 is the product of two Legendre symbols of -1.

Theorem 1
Let n be an odd positive integer. Let a be such that \text{GCD}(a,n)=1. Then If a is a quadratic residue modulo n, then \displaystyle  \biggl(\frac{a}{n}\biggr)=1. The converse does not hold if n is not a prime.

Proof
Suppose that a is a quadratic residue modulo n, i.e. the equation x^2 \equiv a \ (\text{mod} \ n) has a solution. Let n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t} be the prime factorization of n. Let m_i=p_i^{e_i} for each i. By the Chinese remainder theorem, the equation x^2 \equiv a \ (\text{mod} \ m_i) has a solution for each i=1,2,\cdots,t. it then follows that the equation x^2 \equiv a \ (\text{mod} \ p_i) has a solution too for each i=1,2,\cdots,t. Hence the Legendre symbol \displaystyle  \biggl(\frac{a}{p_i}\biggr)=1 for each i. It follows that the Jacobi symbol \displaystyle  \biggl(\frac{a}{n}\biggr)=1. \square

For the second question, the rules that are obeyed by the Legendre symbol are also obeyed by the Jacobi symbol. Some of the rules are easily seen to carry over to the Jacobi symbol. The fact that the law of quadratic reciprocity and the two supplements are obeyed by the Jacobi symbol is not entirely obvious from the definition. However the proof is not difficult. We give a complete proof here.

Lemma 2
Let a and b be odd positive integers. The following two conditions hold.

    \displaystyle \frac{a-1}{2} \times \frac{b-1}{2} \equiv \frac{ab-1}{2} \ (\text{mod} \ 2)

    \displaystyle \frac{a^2-1}{8} \times \frac{b^2-1}{8} \equiv \frac{(ab)^2-1}{8} \ (\text{mod} \ 2)

Proof
The lemma is established by the following derivation:

    \displaystyle \frac{ab-1}{2}-\biggl[\frac{a-1}{2}+\frac{b-1}{2} \biggr]=\frac{ab-a-b+1}{2}=\frac{(a-1)(b-1)}{2}

    \displaystyle \frac{(ab)^2-1}{8}-\biggl[\frac{a^2-1}{8}+\frac{b^2-1}{8} \biggr]=\frac{(ab)^2-a^2-b^2+1}{8}=\frac{(a^2-1)(b^2-1)}{8}

Because both a and b are odd integers, the right-hand-side of both equations are even integers and thus \equiv 0 \ (\text{mod} \ 2). \square

Theorem 3 (Properties of Jacobi Symbol)

  1. \displaystyle  \biggl(\frac{a}{n}\biggr) = \left\{ \begin{array}{rl}           0 &\ \text{if } \text{GCD}(a,n) >1 \\          \pm 1 &\ \text{if } \text{GCD}(a,n)=1 \end{array} \right.
  2. \text{ }

  3. If n is a prime, then the Jacobi symbol \displaystyle  \biggl(\frac{a}{n}\biggr) coincides with the Legendre symbol \displaystyle  \biggl(\frac{a}{n}\biggr).
  4. \text{ }

  5. If a \equiv b \ (\text{mod} \ n), then \displaystyle  \biggl(\frac{a}{n}\biggr)=\biggl(\frac{b}{n}\biggr).
  6. \text{ }

  7. The Jacobi symbol is multiplicative when the bottom argument is fixed, i.e. \displaystyle  \biggl(\frac{ab}{n}\biggr)=\biggl(\frac{a}{n}\biggr) \biggl(\frac{b}{n}\biggr).
  8. \text{ }

  9. The Jacobi symbol is multiplicative when the upper argument is fixed, i.e. \displaystyle  \biggl(\frac{a}{mn}\biggr)=\biggl(\frac{a}{m}\biggr) \biggl(\frac{a}{n}\biggr).
  10. \text{ }

  11. (The law of quadratic reciprocity)
    Let a and b be relatively prime odd positive integers. Then

      \displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)=(-1)^{(a-1)/2 \times (b-1)/2}

      Equivalently, \displaystyle  \biggl(\frac{a}{b}\biggr) = \left\{ \begin{array}{rl}           \displaystyle  \biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv 1 \ (\text{mod} \ 4) \text{ or }  b \equiv 1 \ (\text{mod} \ 4) \\         \displaystyle  -\biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv b \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

  12. (First supplement to the law of quadratic reciprocity)
    Let n be an odd positive integer. Then

      \displaystyle  \biggl(\frac{-1}{n}\biggr)=(-1)^{(n-1)/2}.

      Equivalently, \displaystyle  \biggl(\frac{-1}{n}\biggr) = \left\{ \begin{array}{rl}           1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 4) \\         -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

  13. (Second supplement to the law of quadratic reciprocity)
    Let n be an odd positive integer. Then

      \displaystyle  \biggl(\frac{2}{n}\biggr)=(-1)^{(n^2-1)/8}.

      Equivalently, \displaystyle  \biggl(\frac{2}{n}\biggr) = \left\{ \begin{array}{rl}           1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 8) \text{ or } n \equiv 7 \ (\text{mod} \ 8) \\         -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 8) \text{ or } n \equiv 5 \ (\text{mod} \ 8) \end{array} \right.

Proof
For the first bullet point, if the top argument and the bottom argument have a prime factor in common, then one of the Legendre symbols that make up the Jacobi symbol is zero. If the top argument and the bottom argument have no prime factor in common, then all the Legendre symbols that make up the Jacobi symbol is either 1 or -1.

The second point is clear. If the bottom argument is an odd prime, the definition of Jacobi symbol leads to the Legendre symbol.

For bullet points 3, 4 and 5, simply write out the Jacobi symbol and then use the corresponding properties of the Legendre symbol.

Now the proof of bullet point 6 (the law of quadratic reciprocity). Let a and b be relatively prime. Let a=p_1 \times p_2 \times \cdots \times p_w and b=q_1 \times q_2 \times \cdots \times q_t be their prime factorizations. Note that the primes p_i are not necessarily distinct and the primes q_i are not necessarily distinct. However, p_i \ne q_j since a and b are relatively prime. Consider the following derivation of the product \displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr).

    \displaystyle \begin{aligned}\biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)&=\prod \limits_{i=1}^t \biggl(\frac{a}{q_i}\biggr) \ \prod \limits_{j=1}^w \biggl(\frac{b}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{j=1}^w \prod \limits_{i=1}^t \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{i=1}^t \prod \limits_{j=1}^w \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w (-1)^{(p_j-1)/2 \times (q_i-1)/2} \\&=(-1)^E \end{aligned}

    where

    \displaystyle E=\sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]

The bullet point 6 is established after the quantity E is simplified as follows:

    \displaystyle \begin{aligned} \sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]&=\sum_j \biggl[\sum_i \frac{q_i-1}{2}\biggr] \frac{p_j-1}{2} \\&\equiv \sum_j \biggl[ \frac{b-1}{2}\biggr] \frac{p_j-1}{2} \ \ \ \text{ Use Lemma 2}\\&\equiv \frac{b-1}{2} \sum_j  \frac{p_j-1}{2} \\&\equiv \frac{b-1}{2} \frac{a-1}{2} \ (\text{mod} \ 2) \ \ \ \text{ Use Lemma 2}  \end{aligned}

Now consider the bullet point #7 (the first supplement to the law of quadratic reciprocity). The proof is an induction proof on the number of prime factors of n. If n is a prime, then it is done. So we assume n=p_1 \times p_2 (not necessarily distinct). Consider the following derivation:

    \displaystyle \begin{aligned} \biggl(\frac{-1}{n}\biggr)&=\biggl(\frac{-1}{p_1}\biggr) \biggl(\frac{-1}{p_2}\biggr) \\&=(-1)^{(p_1-1)/2} \ (-1)^{(p_2-1)/2} \\&=(-1)^{(p_1-1)/2+(p_2-1)/2} \\&\equiv (-1)^{(p_1 \times p_2 -1)/2} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n -1)/2} \ (\text{mod} \ 2) \end{aligned}

It is a straightforward argument that whenever the property is true for n being a product of k primes, the property is true for n being a product of k+1 primes. Thus bullet 7 is established.

The proof of bullet point 8 (the second supplement to the law of quadratic reciprocity) is also an induction proof on the number of prime factors of n. The most important case is the of two prime factors.

    \displaystyle \begin{aligned} \biggl(\frac{2}{n}\biggr)&=\biggl(\frac{2}{p_1}\biggr) \biggl(\frac{2}{p_2}\biggr) \\&=(-1)^{(p_1^2-1)/8} \ (-1)^{(p_2^2-1)/8} \\&=(-1)^{(p_1^2-1)/8+(p_2^2-1)/8} \\&\equiv (-1)^{((p_1 \times p_2)^2 -1)/8} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n^2 -1)/8} \ (\text{mod} \ 2) \end{aligned}

With the 2-case established, it is straightforward to carry out the remainder of the induction proof of bullet 8. \square

____________________________________________________________________________

Examples

Example 1
Evaluate \displaystyle  \biggl(\frac{1783}{7523}\biggr), an example where both the upper and lower arguments are primes. In the previous post, the example is calculated using only Legendre symbol. Here we work it in Jacobi symbol. As much as possible, we flip the symbol without factoring.

    \displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \ \ *\\&=\biggl(\frac{1783}{391}\biggr) \\&=\biggl(\frac{219}{391}\biggr) \ \ *\\&=-\biggl(\frac{391}{219}\biggr) \\&=-\biggl(\frac{172}{219}\biggr) \\&=-\biggl(\frac{2}{219}\biggr)^2 \biggl(\frac{43}{219}\biggr) \\&=-\biggl(-1\biggr)^2 (-1) \biggl(\frac{219}{43}\biggr) \\&=\biggl(\frac{4}{43}\biggr) \\&=1 \end{aligned}

One advantage of using Jacobi symbol is that when the upper argument is an odd integer that is not prime, we can still flip it (the steps with *). Then reduce and then flip again until we reach a point with small numbers. Thinking in Legendre symbol only, the steps with * cannot be flipped. As Jacobi symbols, they can be flipped freely as long as the arguments are odd integers. The advantage may not be apparent in this example. When the composite integers are large to the point that their factorizations are in effect not obtainable, this advantage is huge. \square

Example 2
Evaluate \displaystyle  \biggl(\frac{a}{p}\biggr) where p= 1298351, an odd prime and a= 756479. This is Example 2 in this previous post. The number a is not a prime. Here we use Jacobi symbol to demonstrate that factoring is not needed. We can start by flipping. We have the following derivation.

    \displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=-\biggl(\frac{1298351}{756479}\biggr) \\&=-\biggl(\frac{541872}{756479}\biggr) \\&=-\biggl(\frac{2}{756479}\biggr)^4 \times \biggl(\frac{33867}{756479}\biggr) \\&=-\biggl(1\biggr)^4 \times (-1) \biggl(\frac{756479}{33867}\biggr)  \\&=\biggl(\frac{11405}{33867}\biggr) \\&=\biggl(\frac{33867}{11405}\biggr) \\&=\biggl(\frac{11057}{11405}\biggr) \\&=\biggl(\frac{11405}{11057}\biggr) \\&=\biggl(\frac{348}{11057}\biggr) \\&=\biggl(\frac{2}{11057}\biggr)^2 \biggl(\frac{87}{11057} \biggr) \\&=\biggl(1\biggr)^2  \biggl(\frac{11057}{87} \biggr) \\&=\biggl(\frac{8}{87}\biggr) \\&=\biggl(\frac{2}{87} \biggr)^3 \\&=1 \end{aligned}

Note that the original symbol to evaluate is a Legendre symbol. The interim steps are done with Jacobi symbol as much as possible. With the Jacobi way, the symbol is flipped, reduced and flipped again multiple times. The derivation seems long. However, the flip-reduce-flip is much faster than factoring when the numbers involved are large. \square

Example 3
Evaluate \displaystyle  \biggl(\frac{a}{n}\biggr) where n= 12408107 and a= 4852777. Both numbers are not prime. The symbol has to be evaluated as a Jacobi symbol.

    \displaystyle \begin{aligned} \biggl(\frac{4852777}{12408107}\biggr)&=\biggl(\frac{12408107}{4852777}\biggr)  \\&= \biggl(\frac{2702553}{4852777}\biggr) \\&= \biggl(\frac{4852777}{2702553}\biggr) \\&= \biggl(\frac{2150224}{2702553}\biggr) \\&= \biggl(\frac{2}{2702553}\biggr)^4 \biggl(\frac{134389}{2702553}\biggr) \\&= \biggl(1\biggr)^4 \biggl(\frac{2702553}{134389}\biggr) \\&= \biggl(\frac{14773}{134389}\biggr) \\&= \biggl(\frac{134389}{14773}\biggr) \\&= \biggl(\frac{1432}{14773}\biggr) \\&= \biggl(\frac{2}{14773}\biggr)^3 \biggl(\frac{179}{14773}\biggr) \\&= \biggl(-1\biggr)^3 \biggl(\frac{14773}{179}\biggr) \\&= - \biggl(\frac{95}{179}\biggr) \\&= - (-1) \biggl(\frac{179}{95}\biggr) \\&=\biggl(\frac{84}{95}\biggr) \\&=\biggl(\frac{2}{95}\biggr)^2 \biggl(\frac{21}{95}\biggr) \\&=\biggl(1\biggr)^2 \biggl(\frac{95}{21}\biggr) \\&=\biggl(\frac{11}{21}\biggr) \\&=\biggl(\frac{21}{11}\biggr) \\&=\biggl(\frac{10}{11}\biggr) \\&=\biggl(\frac{2}{11}\biggr) \biggl(\frac{5}{11}\biggr) \\&=\biggl(-1\biggr) \biggl(\frac{11}{5}\biggr) \\&=-\biggl(\frac{6}{5}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \biggl(\frac{3}{5}\biggr) \\&=-\biggl(-1\biggr) \biggl(\frac{5}{3}\biggr) \\&=\biggl(\frac{2}{3}\biggr) \\&=-1 \end{aligned}

The above derivation seems long in that there are quite a few steps. But many of the steps are flip-reduce-flip-reduce that are easy to do. The steps are all done without factoring, except when the top argument is an even number. The Jacobi symbol \displaystyle  \biggl(\frac{a}{n}\biggr) is -1. In this case, it gives definite information about the status of quadratic nonresidues. We know for sure that a is a quadratic nonresidue modulo the odd integer n, i.e. the equation x^2 \equiv a \ (\text{mod} \ n) has no solutions. \square

Example 4
Evaluate \displaystyle  \biggl(\frac{a}{n}\biggr) where n= 48746413 and a= 17327467. Both numbers are not prime. As in Example 3, the symbol is evaluated using Jacobi symbol.

    \displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{48746413}{17327467}\biggr)  \\&=\biggl(\frac{14091479}{17327467}\biggr) \\&=-\biggl(\frac{17327467}{14091479}\biggr) \\&=-\biggl(\frac{3236168}{14091479}\biggr) \\&=-\biggl(\frac{2}{14091479}\biggr)^3 \biggl(\frac{404521}{14091479}\biggr) \\&=-\biggl(1\biggr)^3 \biggl(\frac{14091479}{404521}\biggr) \\&=- \biggl(\frac{337765}{404521}\biggr) \\&=- \biggl(\frac{404521}{337765}\biggr) \\&=- \biggl(\frac{66756}{337765}\biggr) \\&=- \biggl(\frac{2}{337765}\biggr)^2 \biggl(\frac{16689}{337765}\biggr) \\&=- \biggl(-1\biggr)^2 \biggl(\frac{337765}{16689}\biggr) \\&=-\biggl(\frac{3985}{16689}\biggr) \\&=-\biggl(\frac{16689}{3985}\biggr) \\&=-\biggl(\frac{749}{3985}\biggr) \\&=-\biggl(\frac{3985}{749}\biggr) \\&=-\biggl(\frac{240}{749}\biggr) \\&=-\biggl(\frac{2}{749}\biggr)^4 \biggl(\frac{15}{749}\biggr) \\&=-\biggl(-1\biggr)^4 \biggl(\frac{749}{15}\biggr) \\&=-\biggl(\frac{14}{15}\biggr) \\&=-\biggl(\frac{-1}{15}\biggr)\\&=-(-1)\\&=1 \end{aligned}

The result of \displaystyle  \biggl(\frac{a}{n}\biggr)=1 gives ambiguous information about the status of a= 17327467 being a quadratic residue or nonresidue modulo n= 48746413. In this case, the Jacobi symbol cannot tell us whether the equation x^2 \equiv a \ (\text{mod} \ n) has a solution. In such a case, the only way to know the status of quadratic residue is to know some additional information, namely the factoring of the numbers. This example is small enough that a= 3049 x 5683 and n= 7109 x 6857. With this information, the Jacobi symbol can be set up as follows:

    \displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{17327467}{7109}\biggr) \biggl(\frac{17327467}{6857}\biggr)=(-1) (-1)=1   \end{aligned}

By knowing the factoring of n, the original Jacobi symbol is a product of two Legendre symbols. It can be shown that both of these Legendre symbols are -1. These two Legendre symbols corresponds to these two equations: x^2 \equiv a \ (\text{mod} \ 7109) and x^2 \equiv a \ (\text{mod} \ 6857). The Legendre values of -1 indicate that these two equations have no solutions. By the Chinese remainder theorem, the equation x^2 \equiv a \ (\text{mod} \ 7109 \times 6857) has no solutions. Hence a= 17327467 is a quadratic nonresidue modulo n= 48746413=7109 x 6857. \square

____________________________________________________________________________

Comments

One versatile feature of the Jacobi symbol is that it can be used in evaluating the Legendre symbol, as shown in Example 1 and Example 2. The original Legendre symbol in Example 1 have arguments that are both odd prime and thus can be flipped right away. However, there are numbers in the interim steps that are odd and not prime. With the use of the Jacobi symbol, these interim numbers do have to be factored. The original Legendre symbol in Example 2 has a top argument that is odd and not prime. Treating it as a Jacobi symbol, it can be flipped right away. When numbers involved in Legendre symbol evaluation are large such that the factoring is not obtainable, the Jacobi symbol can be flipped and reduced and flipped again to obtain the answer of the Legendre symbol. The Jacobi symbol plays an outsize role in the evaluation of the Legendre symbol and thus is a pivotal tool in determining whether a number is a quadratic residue modulo an odd prime p or the solvability of the equation x^2 \equiv a \ (\text{mod} \ p).

Example 3 shows that when the Jacobi symbol produces the value of -1, the top argument a is a quadratic nonresidue modulo the lower argument n. Example 4 shows that when the Jacobi symbol produces the value of 1, the picture is murky. In such a case, settling the question of whether the top argument a is a quadratic nonresidue modulo the lower argument n requires additional information. Example 4 shows that if we can factor the lower argument n, then evaluating the individual Legendre symbols (based on the prime factors) will help answer the original question. This points to the possibility that solving the equation x^2 \equiv a \ (\text{mod} \ n) is not feasible when the factorization of a large composite modulus n is not obtainable.

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

The Legendre symbol

The law of quadratic reciprocity is a beautiful result. It is also an excellent tool to answer the question: given an odd prime p, and given that a is an integer such that a and p are relatively prime, is a is a quadratic residue modulo p, in other words, is the equation x^2 \equiv a \ (\text{mod} \ p) solvable? Using the law of quadratic reciprocity requires the evaluation of the Legendre symbol. The focus of this post is on the Legendre symbol as well as related concepts of quadratic residues and the law of quadratic residues. The versatility of the law of quadratic reciprocity is demonstrated with examples.

____________________________________________________________________________

Quadratic Residues

The setting is that the modulus in question is an odd prime p. Consider an integer a such that a and p are relatively prime, i.e. having no common prime factor. The number a is said to be a quadratic residue modulo p if the equation x^2 \equiv a \ (\text{mod} \ p) has an integer solution in x. Another way to say this is that a is a quadratic residue modulo p if there exists a square root of a modulo p (a square root would be a solution to the equation). If the integer a is not a quadratic residue modulo p, we say that a is a quadratic nonresidue modulo p. If the context is clear, the word quadratic can be omitted. We can then say a is a residue modulo p or a is a nonresidue modulo p.

Since every integer is congruent modulo p to one of the numbers in the set \mathbb{Z}_p=\left\{0,1,2,\cdots,p-1 \right\}, the integers a can be considered from the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\} (the non-zero elements of \mathbb{Z}_p).

Let’s look at a quick example. Let p=11. Squaring each number in \mathbb{Z}_{11} produces the set \left\{0^2,1^2,2^2,\cdots,10^2 \right\}. Reducing modulo 11 produces the set \left\{0,1,4,9,5,3 \right\}. Thus the integers 1, 3, 4, 5 and 9 are quadratic residues modulo 11. The square roots of each residue are the solutions to the equation x^2 \equiv a \ (\text{mod} \ 11). For a=3, the solutions are x = 5 and 6. There are two square roots of 3 modulo 11, namely 5 and 6.

When the modulus is small, it is easy to find all quadratic residues simply by squaring all the numbers in \mathbb{Z}_p^*. The focus in this post is on how to use the law of quadratic reciprocity to determine whether a given a is a quadratic residue modulo a large odd prime p.

To check whether the integer a is a quadratic residue modulo an odd prime p, the most important idea, before considering the law of reciprocity, is to check the modular exponentiation a^{(p-1)/2} \ (\text{mod} \ p). If the result is congruent to 1 modulo p, then a is a quadratic residue modulo p. If the result is congruent to -1 modulo p, then a is a quadratic nonresidue modulo p. This is called Euler’s Criterion (proved here). For clarity, it is stated below.

Theorem 1 (Euler’s Criterion)
Let p be an odd prime. Let a be an integer that is relatively prime to p. Then the integer a is a quadratic residue modulo p if and only if \displaystyle a^{(p-1)/2} \equiv 1 \ (\text{mod} \ p). On the other hand, the integer a is a quadratic nonresidue modulo p if and only if \displaystyle a^{(p-1)/2} \equiv -1 \ (\text{mod} \ p).

According to Euler’s Criterion, the task of checking for the status of quadratic residue is a matter of performing a modular exponentiation. This can be done using software or a calculator for modular arithmetic. If so desired, the exponentiation can also be programmed using the fast powering algorithm.

Though Euler’s Criterion (with a calculator for modular arithmetic) is a sure fire way for checking the status of quadratic residues, the law of quadratic reciprocity can simplify the task even further. As the examples below will show, checking the status of quadratic residues using the law of reciprocity may require no modular exponentiation at all and if exponentiation is required, it is of a much smaller size.

Euler’s Criterion also gives us several basic facts about quadratic residues.

Theorem 2
Let p be an odd prime. The following properties are true:

  • If a and b are both residues modulo p, then the product a \times b is a residue modulo p.
  • If If a and b are both nonresidues modulo p, then the product a \times b is a residue modulo p.
  • If a and b are such that one of them is a residue modulo p and the other is a nonresidue modulo p, then the product a \times b is a nonresidue modulo p.

Theorem 2 says that the product of two integers of the same types (both residues or both nonresidues) is always a residue modulo the odd prime p. The product of two integers of different types is always a nonresidue modulo the odd prime p. The theorem follows from Euler’s criterion and from the fact that (ab)^{(p-1)/2}=a^{(p-1)/2} \times b^{(p-1)/2}.

In arithmetic modulo a prime p, there exists a primitive root modulo p and that any primitive root generates by powering all the integers that are relatively prime to the modulus p. Let g be a primitive root modulo an odd prime p. It then follows that the quadratic residues modulo p are the even powers of g and the nonresidues are the odd powers of g. A related fact is that when p is an odd prime and when a and p are relatively prime, the equation x^2 \equiv a \ (\text{mod} \ p) either has two solutions or has no solutions.

Theorem 3
Let g be a primitive root modulo an odd prime p. For any a that is relatively prime to p, the following is true:

  • a is a quadratic residue modulo p if and only if a is of the form a \equiv g^{2k} \ (\text{mod} \ p) for some positive integer k,
  • a is a quadratic nonresidue modulo p if and only if a is of the form a \equiv g^{2k+1} \ (\text{mod} \ p) for some positive integer k.
  • (proved here)

Theorem 4
Let p be an odd prime. For any a that is relatively prime to p, the equation x^2 \equiv a \ (\text{mod} \ p) either has two solutions or has no solutions (proved here).

____________________________________________________________________________

Legendre Symbol

The law of quadratic reciprocity is stated using the Legendre symbol. For an odd prime p and for an integer a that is relatively prime to p, the symbol \displaystyle \biggl(\frac{a}{p}\biggr) is defined as follows:

    \displaystyle  \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl}                      1 &\ \text{if }  a  \text{ is a quadratic residue modulo }p\\          -1 &\ \text{if }  a  \text{ is a quadratic nonresidue modulo }p \end{array} \right.

One obvious and important observation is that Euler’s Criterion can be restated as follows:

Theorem 1a (Euler’s Criterion)
Let p be an odd prime. Let a be an integer that is relatively prime to p. Then \displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p).

In the above definition, the lower argument of the Legendre symbol is always an odd prime and the upper argument is an integer that is relatively prime to the lower argument. To smooth out some statements involving the Legendre symbol and to make it easier to define the Jacobi symbol in the next post, we relax the Legendre symbol by making \displaystyle \biggl(\frac{a}{p}\biggr)=0 whenever a and p are not relatively prime, i.e. a \equiv 0 \ (\text{mod} \ p). The Legendre symbol can be broaden slightly by the following:

    \displaystyle  \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl}           0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\           1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic residue modulo }p\\          -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic nonresidue modulo }p \end{array} \right.

Here’s some useful basic facts about the Legendre symbol.

Theorem 5
Let p be an odd prime. The following properties hold:

  • The Legendre symbol is periodic with respect to the top argument, i.e. if a \equiv b \ (\text{mod} \ p), then \displaystyle \biggl(\frac{a}{p}\biggr)=\biggl(\frac{b}{p}\biggr).
  • The Legendre symbol is multiplicative with respect to the top argument, i.e. \displaystyle \biggl(\frac{ab}{p}\biggr)=\biggl(\frac{a}{p}\biggr) \times \biggl(\frac{b}{p}\biggr).
  • If a \equiv 0 \ (\text{mod} \ p), then \displaystyle  \biggl(\frac{a^2}{p}\biggr)=0. If a \not \equiv 0 \ (\text{mod} \ p), then \displaystyle  \biggl(\frac{a^2}{p}\biggr)=1.

The first bullet point in Theorem 5 is easily verified based on the definition of the Legendre symbol. For the case a \equiv 0 \ (\text{mod} \ p), the other facts in Theorem 5 are easily verified. For the case a \not \equiv 0 \ (\text{mod} \ p), the second bullet point follows from Theorem 2, i.e. the fact that the product of two residues and the product of two nonresidues are both residues modulo an odd prime and that the product of a residue and a nonresidue is a nonresidue modulo an odd prime. The second part of the third bullet point is true since any integer that is a square is a quadratic residue.

____________________________________________________________________________

Law of Quadratic Reciprocity

The law of reciprocity can ease the calculation of the Legendre symbol when both the upper and lower arguments are distinct odd primes. Theorem 6 is the law of reciprocity and Theorem 7 and Theorem 8 are two supplements to the law that can round out the calculation. After stating the theorems, we demonstrate with some examples.

Theorem 6 (the law of quadratic reciprocity)

    Let p and q be two distinct odd prime numbers. Both of the following statements hold.

      \displaystyle  \biggl(\frac{q}{p}\biggr) \displaystyle \biggl(\frac{p}{q}\biggr)=(-1)^{(p-1)/2 \times (q-1)/2}

      Equivalently and more explicitly,

      \displaystyle  \biggl(\frac{q}{p}\biggr) = \left\{ \begin{array}{rl}                      \displaystyle \biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \text{ or } q \equiv 1 \ (\text{mod} \ 4)\\          \displaystyle  -\biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv q \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

Theorem 7 (first supplement to the law of quadratic reciprocity)

    Let p be an odd prime number. The following statement holds.

      \displaystyle  \biggl(\frac{-1}{p}\biggr) = (-1)^{(p-1)/2} = \left\{ \begin{array}{rl}                      1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 4)\\          -1 &\ \text{if } p \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

Theorem 8 (second supplement to the law of quadratic reciprocity)

    Let p be an odd prime number. The following statement holds.

      \displaystyle  \biggl(\frac{2}{p}\biggr) =(-1)^{(p^2-1)/8}= \left\{ \begin{array}{rl}                      1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 8) \text{ or } p \equiv 7 \ (\text{mod} \ 8)\\          -1 &\ \text{if } p \equiv 3 \ (\text{mod} \ 8) \text{ or } p \equiv 5 \ (\text{mod} \ 8) \end{array} \right.

Theorem 6 shows how to flip the Legendre symbol if both the upper and lower arguments are distinct odd primes. As long as one of the primes is congruent to 1 modulo 4, we can safely flip the symbol. If both primes are not congruent to 1 modulo 4, we can still flip the symbol except that we have to attach a minus sign. Theorem 7 (the first supplement) indicates when -1 (or p-1) is a quadratic residue an odd prime p. In words, -1 is a residue modulo p if dividing p by 4 gives the remainder of 1. Otherwise -1 is a nonresidue modulo p. Theorem 8 (the second supplement) indicates when 2 is a residue modulo an odd prime p. In words, 2 is a residue modulo p if dividing p by 8 leaves a remainder of 1 or 7. Otherwise 2 is a nonresidue modulo p.

____________________________________________________________________________

Examples

Example 1
Evaluate \displaystyle  \biggl(\frac{1783}{7523}\biggr), an example where both the upper and lower arguments in the Legendre symbol are primes.

    \displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \\&=-\biggl(\frac{17}{1783}\biggr) \times \biggl(\frac{23}{1783}\biggr) \\&=-\biggl(\frac{1783}{17}\biggr) \times (-1) \biggl(\frac{1783}{23}\biggr) \\&=\biggl(\frac{15}{17}\biggr) \times \biggl(\frac{12}{23}\biggr) \\&=\biggl(\frac{3}{17}\biggr) \times \biggl(\frac{5}{17}\biggr) \times \biggl(\frac{2}{23}\biggr)^2 \times \biggl(\frac{3}{23}\biggr) \\&=\biggl(\frac{17}{3}\biggr) \times \biggl(\frac{17}{5}\biggr) \times \biggl(1\biggr)^2 \times (-1)\biggl(\frac{23}{3}\biggr) \\&=-\biggl(\frac{2}{3}\biggr) \times \biggl(\frac{2}{5}\biggr) \times  \biggl(\frac{2}{3}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \\&=-(-1) \\&=1 \end{aligned}

The above derivation is a repeated use of Theorems 5, 6 and 8. The idea is to flip the Legendre symbols to make the lower arguments smaller. Then reduce the upper arguments and then factor the upper arguments. Then flip again until reaching a Legendre symbol of \displaystyle \biggl(\frac{2}{5}\biggr), which is easy to solve.

It then follows that 1783 is a quadratic residue modulo the odd prime 7523. The answer can be confirmed by using Euler’s Criterion. Note that 1783^{3761} \equiv 1 \ (\text{mod} \ 7523). \square

Example 2
Evaluate \displaystyle  \biggl(\frac{a}{p}\biggr) where p= 1298351, an odd prime and a= 756479.

The number a is not a prime and is factored as a=353 \times 2143. We have the following derivation.

    \displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=\biggl(\frac{353}{1298351}\biggr) \times \biggl(\frac{2143}{1298351}\biggr) \\&=\biggl(\frac{1298351}{353}\biggr) \times (-1)\biggl(\frac{1298351}{2143}\biggr) \\&=-\biggl(\frac{17}{353}\biggr) \times \biggl(\frac{1836}{2143}\biggr) \\&=-\biggl(\frac{17}{353}\biggr) \times \biggl(\frac{2}{2143}\biggr)^2 \times \biggl(\frac{3}{2143}\biggr)^3 \times \biggl(\frac{17}{2143}\biggr)  \\&=-\biggl(\frac{353}{17}\biggr) \times \biggl(1\biggr)^2 \times (-1) \biggl(\frac{2143}{3}\biggr)^3 \times \biggl(\frac{2143}{17}\biggr) \\&=\biggl(\frac{13}{17}\biggr) \times  \biggl(\frac{1}{3}\biggr)^3 \times \biggl(\frac{1}{17}\biggr) \\&=\biggl(\frac{17}{13}\biggr) \times  \biggl(1\biggr)^3 \times \biggl(1\biggr) \\&=\biggl(\frac{4}{13}\biggr) \\&=1 \end{aligned}

The evaluation of the Legendre symbols in this example does not start with a flipping since the upper argument 756479 is not a prime. Instead, we start with factoring the upper argument into prime factors and then proceed with a series of flipping, reducing and factoring. \square

Example 3
Evaluate \displaystyle  \biggl(\frac{a}{p}\biggr) where p= 569, an odd prime and a= 1610280.

    \displaystyle \begin{aligned} \biggl(\frac{1610280}{569}\biggr)&=\biggl(\frac{3}{569}\biggr)^4 \times \biggl(\frac{5}{569}\biggr) \times \biggl(\frac{7}{569}\biggr) \times \biggl(\frac{568}{569}\biggr) \\&= \biggl(\frac{569}{3}\biggr)^4 \times \biggl(\frac{569}{5}\biggr) \times \biggl(\frac{569}{7}\biggr) \times \biggl(\frac{-1}{569}\biggr) \\&= \biggl(\frac{2}{3}\biggr)^4 \times \biggl(\frac{4}{5}\biggr) \times \biggl(\frac{2}{7}\biggr) \times \biggl(1\biggr) \\&= \biggl(-1\biggr)^4 \times \biggl(1\biggr) \times \biggl(1\biggr) \\&=1 \end{aligned}

This example can also be evaluated by first reducing 1610280 modulo 569. \square

____________________________________________________________________________

Comment

The law of quadratic reciprocity is a deep and powerful result. It guides the evaluation of Legendre symbols in an attempt to answer whether a number is a quadratic residue modulo an odd prime. The law of reciprocity as represented above requires that the lower argument in the Legendre symbol is an odd prime. When the upper argument is an odd number that is not a prime, there is no way to flip it (based on the law of reciprocity using the Legendre symbol). In Example 2, the evaluation of the Legendre symbol cannot begin until the top argument is factored. The factoring in Example 2 is possible since the number is small. When the number is large, factoring may not always be feasible. It turns out that the Legendre symbol has a generalization, called the Jacobi symbol, that is even more versatile and is defined in the next post.

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}