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

where is an odd prime and is an integer that is relatively prime to . When equation (1) has a solution, the number is said to be a quadratic residue modulo . Any solution of equation (1) is called a square root of modulo . When the equation has no solutions, the number is said to be a quadratic nonresidue modulo . 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 is small (prime or composite), then it is easy to solve equation (1). Simply square each element in the set modulo and look for the value . 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 . The case is easy to deal with. Thus in solving equations described in (1), the focus is on odd primes and on integers that are relatively prime to .

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 is a quadratic residue modulo . The algorithm is to evaluate the Legendre symbol (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 , exactly half of the elements in the set are quadratic residues modulo . In other words, modulo an odd prime , there are many quadratic residues and 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 , there is an explicit formula that gives the solutions to equation (1). For odd prime , no explicit formula exists. For the case of , 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 (**RES**idues **SOL**ver). 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. . In this case, the solutions to equation (1) are given by where

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

On the surface, it appears that the above derivation works for all primes. Note that the exponent must be an integer. The assumption makes it an integer. Using Euler’s Criterion, the quantity is replaced by the Lengendre symbol, which is a 1 since is a quadratic residue modulo .

As a quick example, let’s solve the equation . The prime 431 is congruent to 3 modulo 4. The number 19 is a quadratic residue modulo 431. One solution is given by . 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 . Obviously, we need to check that the number is a quadratic residue modulo . This can be done by evaluating the Legendre symbol .

____________________________________________________________________________

**Tonelli-Shanks Algorithm**

** Objective**: to solve the equation where is an odd prime satisfying and is a quadratic residue modulo , i.e. the Legendre symbol .

** Steps**:

- Factor out the largest power of 2 from the even integer , i.e. obtain where is odd.
- Find a positive integer that is a quadratic nonresidue modulo , i.e. find such that .
- Calculate the following four quantities:
- Loop
- If , then the algorithm stops and output and , the two solutions of the equation. If , then perform the following two steps.
- Find the least such that and such that .
- Calculate and replace the quantities , , and as follows:
Go back to Step A.

The initial value of 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 . Each time a new value of is calculated, the order of the new is smaller than the order of the previous . The goal is to reach a of order 1, which means that the number itself would be , at which point the estimate becomes a solution. Let’s consider some examples.

____________________________________________________________________________

**Examples**

*Example 1*

Solve the equation .

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

Step 1. and since 592 = 16 x 37.

Step 2. is a quadratic nonresidue modulo 593.

Step 3. Calculate the following four quantities:

_______________________________________

The above is obviously . We now find the least , , such that . In other words, repeatedly square until reaching the value of 1. The result is . Let . Replace the quantities , , and as follows:

_______________________________________

The last is obviously . We now find the least , , such that . The result is . Note that the order of goes from previously to .

Let . Replace the quantities , , and as follows:

Now we reach . The solutions to the equations are: 263 and 330 (=593 – 263).

*Example 2*

Solve the equation where 2795830049 and 2262876953.

The number is a prime and the value of the Legendre symbol is . The following shows the steps.

Step 1. and 87369689.

Step 2. is a quadratic nonresidue modulo . This is the result of a search starting with 2.

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

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

_______________________________________

Iteration 1

- , the least such that .

_______________________________________

Iteration 2

- , the least such that .

_______________________________________

Iteration 3

- , the least such that .

_______________________________________

Solutions

____________________________________________________________________________

**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 and are relatively prime to an odd prime number . Suppose that the order of modulo is with being a positive integer. Suppose that the order of modulo is also . Then the order of modulo is where .

*Proof*

Since the order of is , . Note that . Then it must be that since the equation has only two solutions. By a similar argument, . Consider the following:

This means that the order of divides . Thus the order of modulo must be for some .

*Proof of Tonelli-Shanks algorithm*

Since is an odd prime, we set where is odd. We also select a positive integer that is a quadratic nonresidue modulo . To start the calculation, obtain the following four quantities:

The quantity is an initial estimate of the desired solution since

If , then would be a solution and the algorithm stops. So assume that . Then we begin a loop to fine tune until reaching a step with .

To make sense of the loop in the algorithm, consider the quantity and the quantity . First of all, the integer has order modulo , as shown below.

Furthermore, the order of modulo is less or equal to since as shown below.

Let be the order of where . Now begin the calculation for the first iteration of the loop. First, calculate .

One important point to make is that the order of modulo is the same as the order of , which is . The following shows why.

By the lemma, the order of is for some . Note that

In light of the above, if , then is a solution and the algorithm stops. Even if , there is progress since the order of is less than the previous with . Repeat the loop to obtain with the order of being where . When the order of is 1, . When the modulus is a prime, there is only one element with order 1, namely the element 1. Then the quantity is a solution to the given equation.

To further illustrate, we perform one more iteration of the loop. Let . Calculate the following four quantities:

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

By the lemma, the order of is for some . Note the following:

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

____________________________________________________________________________

**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 and the quadratic residue modulo . The two inputs are translated to the three quantities , and where is the number of digits in the binary representation of the odd prime , is the number of ones in the binary representation of and is the largest power of 2 in the factor of . 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:

Another consideration is the selection of , a quadratic nonresidue modulo , which can be found by checking random selections from the set . 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 = 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

is difficult to solve where the modulus is the product of two large primes and . In fact the Rabin cryptosystem is based on the difficulty of solving equation (3). However, if the factoring of 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 where 3825123056546413057 and 1347234680313589343.

The number is a prime and the value of the Legendre symbol is . The following shows the steps.

Step 1. and 7470943469817213.

Step 2. is a quadratic nonresidue modulo . This is the result of a search starting with 2.

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

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

_______________________________________

Iteration 1

- , the least such that .

_______________________________________

Iteration 2

- , the least such that .

_______________________________________

Iteration 3

- , the least such that .

_______________________________________

Iteration 4

- , the least such that .

_______________________________________

Solutions

____________________________________________________________________________

**Exercises**

We close with some exercises. Use Tonelli-Shanks algorithm to solve the equation for each of the following choices of and .

- and
- and
- and
- and
- and
- and

Solutions are:

- 35 and 158
- 103 and 466
- 19136 and 15233
- 30781 and 19972
- 45733 and 51508
- 1056882643 and 1716794350

____________________________________________________________________________