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 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, 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, 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.

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. 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. 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$

____________________________________________________________________________

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}$