Square roots

The Fiat-Shamir protocol is based on taking squares in modular arithmetic. That is easy to compute. The inverse operation of taking square roots can be much harder. It is fairly easy to compute $107^2\pmod{257}$, even by hand, but finding a number x such that $x^2 \equiv 107 \pmod {257}$ is much more difficult. That is what we mean by taking the square root of 107 modulo 257. Do not even think about computing $\sqrt{107}$ on your calculator; it will have nothing to do with computing the modular square root. The number $\sqrt{107} = 10.34408...$ (oops, I calculated it on my calculator; sorry) is an endless real number that can't be correlated with an integer mod 257. We must use an entirely different way of thinking for modular square roots.

In the case of a prime modulus, there are some methods for computing modular square roots. That is on account of the primitive root g, which we said previously must exist. Every number relatively prime to 257 is a power of g. If we would like to compute the square root of a, first we find a primitive root g and then we find the power $a\equiv g^k \pmod p$. (This is sometimes called the discrete logarithm; finding an exponent is always something like finding a logarithm.) Now if $a\equiv x^2$ and $x\equiv g^l$, then by squaring we see that g^k = g^2l. The truth is now clear: a will have a square root only if its exponent k is even. Dividing the exponent by 2 gives the exponent of the square root.

As a first example, consider finding the square root of 6 modulo 19. From the table 8.1 at the beginning of this section we see that $6\equiv 3^8 \pmod{19}$. Then a square root is $3^4\equiv 5 \pmod {19}$. Sure enough, we may check that $5^2=25 \equiv 6 \pmod{19}$. Just as in the process of computing ordinary square roots, there is a second square root, too, namely $-5\equiv 14 \pmod{19}$.

There is a very simple way to exploit this to find a square root in the case that the prime p is congruent to 3 modulo 4. These would be primes like 7, 11, 19, 31, 43, etc. In that case, $k=\frac{p+1}{4}$is an integer; for example $\frac{7+1}{4} =2$. Suppose $a\equiv x^2 \pmod p$. Then

$$a^{\frac{p+1}{4}} \equiv (x^2)^{\frac{p+1}{4}} = x^{\frac{p+1}{2}} = x \cdot x^{\frac{p-1}{2}} \pmod p$$

This is prompted by Fermat's theorem which says $x^{p-1}\equiv 1 \pmod p$. Since p is odd, p-1 is even. Then $(x^{\frac{p-1}{2}})^2 = x^{p-1} \equiv 1 \pmod p$, the power $x^{\frac{p-1}{2}}$ is a square root of 1. Those are easy to compute: 1 and -1. Put these together and you will see that the $\frac{p+1}{4}$ power of a is bound to be a square root of a (if it has one).

The case p congruent to 1 modulo 4 is more complicated, but there are fast methods for computing square roots in that case as well. The general modulus m is a different matter. However, the congruence $a\equiv x^2 \pmod m$ implies the congruence $a\equiv x^2 \pmod{p^n}$for any prime power divisor pⁿ of m. The topic of the next section, the Chinese Remainder Theorem, will imply the converse is true. Thus, solving $x^2 \equiv a \pmod m$ may be reduced to solving the same congruence for each prime power divisor of m.

Before turning to the Chinese Remainder Theorem, we will end with the setup of one problem. Exercise 5 in Chapter 3 of [Beutelspacher, 1994] poses the congruence $x^2\equiv 34 \pmod {55}$. The number 555 factors as $5\times 11$, therefore our previous discussion would suggest working with the two congruences $x^2\equiv 34 \equiv 4 \pmod 5$ and $x^2\equiv 34\equiv 1 \pmod {11}$. These are very easy to solve for x. Now we just have to piece the solutions together to find the solution for modulus 55.