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
*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 . 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
.
Suppose
.
Then

This is prompted by Fermat's theorem which says . Since

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 *p*^{n} 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.