Square Roots Modulo p

note

This is Lab 14 from Clint by Hugh Montgomery, edited by Elad Zelingher. All rights reserved to Hugh Montgomery.

In discussing pseudoprime tests and primitive roots we have generated a circle of ideas that we now harness to give a quick method for finding the roots of the quadratic congruence $x^{2} \equiv a \pmod p$. The algorithm involved is described in detail in §2.9 of NZM. Before confronting the full algorithm, we consider two instructive examples.

Problem 1

If $p \equiv 3 \pmod{4}$ then the solutions of the congruence $x^{2} \equiv a \pmod p$ are given by $x \equiv \pm a^{(p+1) / 4} \pmod p$. For example, suppose we wish to find solutions of the congruence $x^{2} \equiv 2 \pmod{103}$. By using the program Power we find that $2^{26} \equiv 38$ (mod 103). Hence the desired solutions are $\pm 38$, as we may confirm by verifying that $38^{2} \equiv 2 \pmod{103}$. Use the program Power in this way to find the solutions of the congruence $x^{2} \equiv 7 \pmod{103}$. What happens to this procedure if $a$ is a quadratic nonresidue of $p$ ? For example, what happens if you try to use this method to solve the congruence $x^{2} \equiv 3 \pmod{103}$ ? Explain why it is always the case that exactly one of $a$ and $-a$ is a quadratic residue, if $p$ is a prime, $p \equiv 3 \pmod{4}$, and $a \not \equiv 0 \pmod p$.

Problem 2

Suppose that $z$ is a quadratic nonresidue of $p$, so that by Euler's criterion $z^{(p-1) / 2} \equiv-1$ $\pmod p$. If $p \equiv 1 \pmod{4}$ then it follows that solutions of the congruence $x^{2} \equiv-1$ $\pmod p$ are given by $x \equiv \pm z^{(p-1) / 4} \pmod p$. However, to make use of this observation, we need to find the quadratic nonresidue $z$. Rather than give a deterministic algorithm for this, we simply try $z$ at random, until a quadratic nonresidue is found. When $z$ is selected, we compute $x \equiv z^{(p-1) / 4} \pmod p$. Then either $x^{2} \equiv-1 \pmod p$, in which case we are done, or else $x^{2} \equiv 1 \pmod p$ (i.e., $x \equiv \pm 1 \pmod p$ ), in which case we start over with a new value of $z$. Since exactly half of the nonzero residue classes are quadratic nonresidues, the expected number of such trials is 2 . An algorithm of this kind is referred to as a Monte Carlo algorithm, or as a probabilistic algorithm. Since the quadratic nonresidues seem to be randomly distributed between 0 and $p$, we do not take the trouble to use a random-number generator in selecting the values of $z$ : It is enough to try consecutive integers (skipping the perfect squares). For example, $2^{24} \equiv-1 \pmod{97}$, and $3^{24} \equiv-1 \pmod{97}$, but $5^{24} \equiv 22 \pmod{97}$, and hence the solutions of $x^{2} \equiv-1$ $\pmod{97}$ are given by $x \equiv \pm 22 \pmod{97}$.

Problem 3

We now proceed to the general case. To see how one would find the solutions of the congruence $x^{2} \equiv 2 \pmod{97}$, use SqrtDem with input $a=2$ and $p=97$, and follow the prompts. What happens if you input input $a=5$ and $p=97$? To get the same result without all the discussion, use SqrtModP.

Problem 4

Apply the program SqrtDem to various values of $a$ with $p=223497217$. What is the power of 2 dividing $p-1$ ?

Problem 5

Suppose that $p$ is prime and that $p \equiv 2 \pmod{3}$. Explain why $a^{(2 p-1) / 3}$ is the sole solution of the congruence $x^{3} \equiv a \pmod p$. Use this principle and the program Power to determine the unique root of the congruence $x^{3} \equiv 2 \pmod{101}$.

Problem 6

Suppose that $p$ is prime and that $p \equiv 1 \pmod{3}$. Explain how a probabilistic algorithm might be constructed to locate the roots of the congruence $x^{3} \equiv 1 \pmod p$. (Hint: One might $\operatorname{try} x \equiv z^{(p-1) / 3} \pmod p$, where $z$ is chosen randomly.) The congruence in question has exactly 3 roots, say $x_{0}, x_{1}, x_{2}$. Since 1 is one of these roots, we may suppose that $x_{0}=1$. Explain why $x_{2} \equiv x_{1}^{2} \pmod p$, and $x_{1} \equiv x_{2}^{2} \pmod p$. Thus if one of these roots can be found then so can the other. Use your method to find the solutions of the congruence $x^{3} \equiv 1 \pmod{97}$. What is the probability that a given trial will be successful?

Problem 7

For the programmer. Write a program that finds the roots of the congruence $x^{3} \equiv a \pmod p$ .(Hint: Recall Problems 6 and 8 on p. 115 of the text.)

Discussion

The algorithm we have used to take squareroots modulo $p$ was invented by Dan Shanks in 1972; he called it RESSOL, because it SOLves for RESidues. This algorithm is very similar to one described much earlier by Tonelli. Other methods for taking squareroots modulo $p$ have been given by Lehmer (related to earlier work of Cipolla), by Peralta, and by Adleman, Manders, and Miller. In addition, more general algorithms have been devised for factoring a polynomial modulo $p$; such an algorithm could be applied to the polynomial $x^{2}-a$ in order to find the squareroots of $a$ modulo $p$. One such algorithm has been proposed by Berlekamp, but the more recent method of Cantor and Zassenhaus seems to be the method of choice. Among the various methods, it is interesting to note that while Shanks' method is somewhat slower if $p-1$ is divisible by a high power of $p$, Peralta' method, which depends on the arithmetic of polynomials (mod $p$ ), is faster in this case. For more details one may consult the following papers.

• L. Adleman, K. Manders, and G. Miller, On taking roots in finite fields, 18th IEEE Annual Sympos. Foundations of Computer Science, Providence, RI, 1977.
• E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-735.
• D. G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), 587-592.
• D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory (W. J. LeVeque, ed.), Math. Assoc. Amer., 1969.
• R. Peralta, A simple and fast probabilistic algorithm for computing square roots modulo a prime number, IEEE Trans. Info. Thy. IT-32 (1986), 846-848.
• M. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comp. 9 (1980), 273-280.
• D. Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics, 1972, pp. 51-70.