Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3.9 Square Roots Mod n

Suppose we are told that $x^{2} \equiv 71 (mod 77)$ $x^{2} \equiv 71 (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 (mod n),$ $x^{2} \equiv b (mod n),$ where $n = p q$ $n = p q$ is the product of two primes. We show in the following that this can be done quite easily, once the factorization of $n$ $n$ is known. Conversely, if we know all solutions, then it is easy to factor $n .$ $n .$

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

Proposition

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

If $y$ $y$ has a square root mod $p,$ $p,$ then the square roots of $y$ $y$ mod $p$ $p$ are $\pm x .$ $\pm x .$
If $y$ $y$ has no square root mod $p,$ $p,$ then $- y$ $- y$ has a square root mod $p,$ $p,$ and the square roots of $- y$ $- y$ are $\pm x .$ $\pm x .$

Proof. If $y \equiv 0 (mod p),$ $y \equiv 0 (mod p),$ all the statements are trivial, so assume $y \equiv 0 (mod p) .$ $y \equiv 0 (mod p) .$ Fermat’s theorem says that $y^{p - 1} \equiv 1 (mod p) .$ $y^{p - 1} \equiv 1 (mod p) .$ Therefore,

\begin{matrix} x^{4} \equiv y^{p + 1} \equiv y^{2} y^{p - 1} \equiv y^{2} & (mod p) . \end{matrix}

$\begin{matrix} x^{4} \equiv y^{p + 1} \equiv y^{2} y^{p - 1} \equiv y^{2} & (mod p) . \end{matrix}$

This implies that $(x^{2} + y) (x^{2} - y) \equiv 0 (mod p),$ $(x^{2} + y) (x^{2} - y) \equiv 0 (mod p),$ so $x^{2} \equiv \pm y (mod p) .$ $x^{2} \equiv \pm y (mod p) .$ (See Exercise 13(a).) Therefore, at least one of $y$ $y$ and $- y$ $- y$ is a square mod $p .$ $p .$ Suppose both $y$ $y$ and $- y$ $- y$ are squares mod $p,$ $p,$ say $y \equiv a^{2}$ $y \equiv a^{2}$ and $- y \equiv b^{2} .$ $- y \equiv b^{2} .$ Then $- 1 \equiv (a / b)^{2}$ $- 1 \equiv (a / b)^{2}$ (work with fractions mod $p$ $p$ as in Section 3.3), which means $- 1$ $- 1$ is a square mod $p .$ $p .$ This is impossible when $p \equiv 3 (mod 4)$ $p \equiv 3 (mod 4)$ (see Exercise 26). Therefore, exactly one of $y$ $y$ and $- y$ $- y$ has a square root mod $p .$ $p .$ If $y$ $y$ has a square root mod $p$ $p$ then $y \equiv x^{2},$ $y \equiv x^{2},$ and the two square roots of $y$ $y$ are $\pm x .$ $\pm x .$ If $- y$ $- y$ has a square root, then $x^{2} \equiv - y .$ $x^{2} \equiv - y .$

Example

Let’s find the square root of 5 mod 11. Since $(p + 1) / 4 = 3,$ $(p + 1) / 4 = 3,$ we compute $x \equiv 5^{3} \equiv 4 (mod 11) .$ $x \equiv 5^{3} \equiv 4 (mod 11) .$ Since $4^{2} \equiv 5 (mod 11),$ $4^{2} \equiv 5 (mod 11),$ the square roots of 5 mod 11 are $\pm 4 .$ $\pm 4 .$

Now let’s try to find a square root of 2 mod 11. Since $(p + 1) / 4 = 3,$ $(p + 1) / 4 = 3,$ we compute $2^{3} \equiv 8 (mod 11) .$ $2^{3} \equiv 8 (mod 11) .$ But $8^{2} \equiv 9 \equiv - 2 (mod 11),$ $8^{2} \equiv 9 \equiv - 2 (mod 11),$ so we have found a square root of $- 2$ $- 2$ rather than of 2. This is because 2 has no square root mod 11.

We now consider square roots for a composite modulus. Note that

\begin{matrix} x^{2} \equiv 71 & (mod 77) \end{matrix}

$\begin{matrix} x^{2} \equiv 71 & (mod 77) \end{matrix}$

means that

\begin{matrix} x^{2} \equiv 71 \equiv 1 & (mod 7) and x^{2} \equiv 71 \equiv 5 & (mod 11) . \end{matrix}

$\begin{matrix} x^{2} \equiv 71 \equiv 1 & (mod 7) and x^{2} \equiv 71 \equiv 5 & (mod 11) . \end{matrix}$

Therefore,

\begin{matrix} x \equiv \pm 1 & (mod 7) and x \equiv \pm 4 & (mod 11) . \end{matrix}

$\begin{matrix} x \equiv \pm 1 & (mod 7) and x \equiv \pm 4 & (mod 11) . \end{matrix}$

The Chinese remainder theorem tells us that a congruence mod 7 and a congruence mod 11 can be recombined into a congruence mod 77. For example, if $x \equiv 1 (mod 7)$ $x \equiv 1 (mod 7)$ and $x \equiv 4 (mod 11),$ $x \equiv 4 (mod 11),$ then $x \equiv 15 (mod 77) .$ $x \equiv 15 (mod 77) .$ In this way, we can recombine in four ways to get the solutions

\begin{matrix} x \equiv \pm 15, & \pm 29 & (mod 77) . \end{matrix}

$\begin{matrix} x \equiv \pm 15, & \pm 29 & (mod 77) . \end{matrix}$

Now let’s turn things around. Suppose $n = p q$ $n = p q$ is the product of two primes and we know the four solutions $x \equiv \pm a, \pm b$ $x \equiv \pm a, \pm b$ of $x^{2} \equiv y (mod n) .$ $x^{2} \equiv y (mod n) .$ From the construction just used above, we know that $a \equiv b (mod p)$ $a \equiv b (mod p)$ and $a \equiv - b (mod q)$ $a \equiv - b (mod q)$ (or the same congruences with $p$ $p$ and $q$ $q$ switched). Therefore, $p | (a - b)$ $p | (a - b)$ but $q ∤ (a - b) .$ $q ∤ (a - b) .$ This means that $gcd (a - b, n) = p,$ $gcd (a - b, n) = p,$ so we have found a nontrivial factor of $n$ $n$ (this is essentially the Basic Factorization Principle of Section 9.4).

For example, in the preceding example we know that $15^{2} \equiv 29^{2} \equiv 71 (mod 77) .$ $15^{2} \equiv 29^{2} \equiv 71 (mod 77) .$ Therefore, $gcd (15 - 29, 77) = 7$ $gcd (15 - 29, 77) = 7$ gives a nontrivial factor of 77.

Another example of computing square roots mod $n$ $n$ is given in Section 18.1.

Notice that all the operations used above are fast, with the exception of factoring $n .$ $n .$ In particular, the Chinese remainder theorem calculation can be done quickly. So can the computation of the gcd. The modular exponentiations needed to compute square roots mod $p$ $p$ and mod $q$ $q$ can be done quickly using successive squaring. Therefore, we can state the following principle:

Suppose $n = p q$ $n = p q$ is the product of two primes congruent to 3 mod 4, and suppose $y$ $y$ is a number relatively prime to $n$ $n$ that has a square root mod $n .$ $n .$ Then finding the four solutions $x \equiv \pm a, \pm b$ $x \equiv \pm a, \pm b$ to $x^{2} \equiv y (mod n)$ $x^{2} \equiv y (mod n)$ is computationally equivalent to factoring $n .$ $n .$

In other words, if we can find the solutions, then we can easily factor $n;$ $n;$ conversely, if we can factor $n,$ $n,$ we can easily find the solutions. For more on this, see Section 9.4.

Now suppose someone has a machine that can find single square roots mod $n .$ $n .$ That is, if we give the machine a number $y$ $y$ that has a square root mod $n,$ $n,$ then the machine returns one solution of $x^{2} \equiv y (mod n) .$ $x^{2} \equiv y (mod n) .$ We can use this machine to factor $n$ $n$ as follows: Choose a random integer $x_{1} (mod n),$ $x_{1} (mod n),$ compute $y \equiv x_{1}^{2} (mod n),$ $y \equiv x_{1}^{2} (mod n),$ and give the machine $y .$ $y .$ The machine returns $x$ $x$ with $x^{2} \equiv y (mod n) .$ $x^{2} \equiv y (mod n) .$ If our choice of $x_{1}$ $x_{1}$ is truly random, then the machine has no way of knowing the value of $x_{1},$ $x_{1},$ hence it does not know whether $x \equiv x_{1} (mod n)$ $x \equiv x_{1} (mod n)$ or not, even if it knows all four square roots of $y .$ $y .$ So half of the time, $x \equiv \pm x_{1} (mod n),$ $x \equiv \pm x_{1} (mod n),$ but half of the time, $x \equiv \pm x_{1} (mod n) .$ $x \equiv \pm x_{1} (mod n) .$ In the latter case, we compute $gcd (x - x_{1}, n)$ $gcd (x - x_{1}, n)$ and obtain a nontrivial factor of $n .$ $n .$ Since there is a 50% chance of success for each time we choose $x_{1},$ $x_{1},$ if we choose several random values of $x_{1},$ $x_{1},$ then it is very likely that we will eventually factor $n .$ $n .$ Therefore, we conclude that any machine that can find single square roots mod $n$ $n$ can be used, with high probability, to factor $n .$ $n .$

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.9 Square Roots Mod n

Create new playlist

Sign In

Sign Up

Table of Contents for
3.9 Square Roots Mod n