Introduction to Cryptography with Coding Theory, 3rd Edition

3.9 Square Roots Mod n

Suppose we are told that $x^2\equiv 71(\text{mod}77)$ has a solution. How do we find one solution, and how do we find all solutions? More generally, consider the problem of finding all solutions of $x^2\equiv b(\text{mod}n)\text{,}$ where $n=pq$ is the product of two primes. We show in the following that this can be done quite easily, once the factorization of $n$ is known. Conversely, if we know all solutions, then it is easy to factor $n\text{.}$

Let’s start with the case of square roots mod a prime $p\text{.}$ The easiest case is when $p\equiv 3(\text{mod}4)\text{,}$ and this suffices for our purposes. The case when $p\equiv 1(\text{mod}4)$ is more difficult. See [Cohen, pp. 31–34] or [KraftW, p. 317].

Proposition

Let $p\equiv 3(\text{mod}4)$ be prime and let $y$ be an integer. Let $x\equiv y^{(p+1)/4}(\text{mod}p)\text{.}$

1. If $y$ has a square ...