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 , even by hand, but finding a number x such that is much more difficult. That is what we mean by taking the square root of 107 modulo 257. Do not even think about computing on your calculator; it will have nothing to do with computing the modular square root. The number (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 . (This is sometimes called the discrete logarithm; finding an exponent is always something like finding a logarithm.) Now if and , then by squaring we see that gk = g2l. 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 . Then a square root is . Sure enough, we may check that . Just as in the process of computing ordinary square roots, there is a second square root, too, namely .
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,
is an integer; for example
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 implies the congruence for any prime power divisor pn of m. The topic of the next section, the Chinese Remainder Theorem, will imply the converse is true. Thus, solving 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 . The number 555 factors as , therefore our previous discussion would suggest working with the two congruences and . These are very easy to solve for x. Now we just have to piece the solutions together to find the solution for modulus 55.