Square Roots Modulo m

13. Square Roots Modulo $m$#

We will soon come back to factorization and computation of discrete logs, but first we need to learn how to compute square roots in $\mathbb{Z}/m\mathbb{Z}$.

13.1. Squares Modulo Odd Primes#

First, we need to recall some definitions and results from the chapter on powers. Recall Fermat’s Little Theorem:

Theorem 13.1 (Fermat’s Little Theorem)

If $p$ is prime and $p \nmid a$, then $a^{p-1} = 1$ in $\mathbb{Z}/p\mathbb{Z}$ (i.e., $a^{p-1} \equiv 1 \pmod{p}$).

Also, remember that we’ve seen before that if $p$ is prime and $x \in \mathbb{F}_p$ is such that $x^2 = 1$, then $x=1$ or $x=-1$.

Remember also our definition of primitive root:

Theorem 13.2 (Primitive Root Theorem)

Let $p$ be a prime. (Remember then that $\mathbb{F}_p$ is just another way to write $\mathbb{Z}/p\mathbb{Z}$.) Then, there is an element $g \in \mathbb{F}_p^{\times}$ such that every element of $\mathbb{F}_p^{\times}$ is a power of $g$. In other words:

\[\mathbb{F}_p^{\times} = \{1, g, g^2, g^3, \ldots, g^{p-2}\}.\]

Definition 13.1 (Primitive Root)

A $g$ as above is called a primitive root of $\mathbb{F}_p$ or a generator of $\mathbb{F}_p^{\times}$.

We also introduced the order of elements in $\mathbb{Z}/m\mathbb{Z}$:

Definition 13.2 (Order of an Element)

If $a$ is a unit of $\mathbb{Z}/m\mathbb{Z}$, then the order of $a$, usually denoted by $|a|$, is the smallest positive power $k$ such that $a^k = 1$.

So, the order of a primitive root in $\mathbb{F}_p$ is $p-1$.

Finally, we have the following results about orders:

Proposition 13.1

Let $a$ be a unit of $\mathbb{Z}/m\mathbb{Z}$. If $a^k = 1$, for some integer $k$, then $|a| \mid k$. In particular, by Euler's Theorem, we always have that $|a| \mid \varphi(m)$.

Proposition 13.2 (Order of a Power)

Let $a \in (\mathbb{Z}/m\mathbb{Z})^{\times}$ with $|a| = n$. Then, we have that

\[|a^k| = \frac{n}{\gcd(n, k)}.\]

We are now prepared to show the following result:

Proposition 13.3 (Squares in $\mathbb{F}_p$)

Let $p$ be an odd prime and $a \in \mathbb{F}_p$, with $a \neq 0$. Then, we have that $a^{(p-1)/2}$ is either $1$ or $-1$. The former occurs when $a$ is a square in $\mathbb{F}_p$ (i.e., when there is some $b \in \mathbb{F}_p$ such that $a = b^2$) and the latter when $a$ is not a square in $\mathbb{F}_p$.

Proof. First, by Fermat’s Little Theorem, we have that

\[\left( a^{(p-1)/2} \right)^2 = a^{p-1} = 1,\]

and, as observed above, this means that $a^{(p-1)/2}$ must be either $1$ or $-1$.

If $a = b^2$, for some $b \in \mathbb{F}_p$ (and $b \neq 0$, since $a \neq 0$), then, by Fermat’s Little Theorem again, we have that

\[a^{(p-1)/2} = \left( b^2 \right)^{(p-1)/2} = b^{p-1} = 1.\]

Hence, if $a$ is a square, then $a^{(p-1)/2} = 1$.

Now, let $g$ be a primitive root of $\mathbb{F}_p$. If $a = g^k$, where $k$ is even (and so $k/2$ is an integer), then $a$ is a square, namely $a = \left( g^{k/2} \right)^2$. So, if $a$ is not a square, then $k$ must be odd.

So, let $k = 2m + 1$, for some integer $m$. Since $(p-1)/2 \mid (p-1)$ and remembering that for any integer $n$ we have $\gcd(a, b) = \gcd(a - nb, b)$ (as used for the Euclidean Algorithm), we have:

\[\begin{split}\begin{align*} \gcd \left(k \cdot \frac{p-1}{2}, p-1 \right) &= \gcd\left((2m + 1) \cdot \frac{p-1}{2}, p-1 \right) \\[3ex] &= \gcd\left(m \cdot (p-1) + \frac{p-1}{2}, p-1 \right) \\[3ex] &= \gcd\left(m \cdot (p-1) + \frac{p-1}{2} - m(p-1), p-1 \right)\\[3ex] &= \gcd\left(\frac{p-1}{2}, p-1 \right) \\[3ex] &= \frac{p-1}{2}. \end{align*}\end{split}\]

Then, by Proposition 13.2, we have

\[\begin{split}\begin{align*} |a^{(p-1)/2}| &= | g^{k \cdot (p-1)/2} | \\[3ex] &= \frac{|g|}{\gcd \left(k \cdot \frac{p-1}{2}, |g| \right))} \\[3ex] &= \frac{p-1}{\gcd \left(k \cdot \frac{p-1}{2}, p-1 \right)} \\[3ex] &= \frac{p-1}{(p-1)/2} \\[3ex] &= 2. \end{align*}\end{split}\]

Since the order is not $1$, it means that $a^{(p-1)/2} \neq 1$, and hence it must be $-1$.

Note

With fast powering, one can use Proposition 13.3 to relatively quickly decide if an element in $\mathbb{F}_p^{\times}$ is a square. But we will see a better method below, using Quadratic Reciprocity.

The proof of Proposition 13.3 also shows the following:

Proposition 13.4

If $g$ is a primitive root in $\mathbb{F}_p$ and $a \in \mathbb{F}_p^{\times}$, then $a$ is a square if and only if $a = g^k$ with $k$ even. In particular, a random element in $\mathbb{F}_p^{\times}$ has a $50\%$ chance of being a square.

13.2. Quadratic Reciprocity#

13.2.1. Legendre Symbol#

Proposition 13.3 gives a way to determine if some $a \in \mathbb{F}_p^{\times}$ is a square. Here will introduce a more efficient way. We start with the following definition:

Definition 13.3 (Legendre Symbol)

Let $p$ be a prime and $a$ be an integer. Then, the Legendre symbol of $a$ modulo $p$ is given by

\[\begin{split}\left(\frac{a}{p}\right) = \begin{cases} \phantom{-}0, & \text{if $p$ divides $a$}; \\ \phantom{-}1, & \text{if $p$ does not divide $a$ and $a$ is a square in $\mathbb{F}_p$};\\ -1, & \text{if $p$ does not divide $a$ and $a$ is not a square in $\mathbb{F}_p$.} \end{cases}\end{split}\]

Note

If $p$ is an odd prime, then, by Proposition 13.3, we could have defined

\[\left(\frac{a}{p}\right) = a^{(p-1)/2} \quad \text{(computed in $\mathbb{F}_p$).}\]

Here are some immediate properties of the Legendre Symbol:

Proposition 13.5 (Basic Properties of the Legendre Symbol)

We have:

If $a \equiv a' \pmod{p}$, then clearly $\left(\dfrac{a}{p}\right) = \left(\dfrac{a'}{p}\right)$. So, we can assume that $a$ is in $\mathbb{F}_p$.
If $k$ is an odd integer, then ${\left(\dfrac{a}{p}\right)}^k = \left(\dfrac{a}{p}\right)$.
If $p$ does not divide $a$ and $k$ is an even integer, then ${\left(\dfrac{a}{p}\right)}^k = 1$.

We also have the following property:

Proposition 13.6 (Multiplicativity of the Legendre Symbol)

Let $a, b \in \mathbb{F}_p^{\times}$. Then $ab$ is a square in $\mathbb{F}_p^{\times}$ if and only if either both $a$ and $b$ are squares in $\mathbb{F}_p^{\times}$ or neither is. Therefore, we have

\[\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right).\]

Proof. This follows from Proposition 13.4. Let $g$ be a primitive root of $\mathbb{F}_p^{\times}$ and write $a = g^r$, $b = g^s$. Then, $ab = g^{r+s}$ is a square if and only if $r + s$ is even. But this happens if and only if either $r$ and $s$ are both even or both odd, i.e., if and only if $a$ and $b$ are both squares or neither is.

The following theorem, referred as Quadratic Reciprocity, is a very important result in Number Theory. It was proved by C.F. Gauss in 1798.

Theorem 13.3 (Quadratic Reciprocity)

Let $p$ and $q$ be odd primes. Then:

\[\begin{split}\left(\frac{-1}{q}\right) = (-1)^{(q-1)/2} = \begin{cases} \phantom{-}1, & \text{if $q \equiv 1 \pmod{4}$};\\ -1, & \text{if $q \equiv 3 \pmod{4}$}. \end{cases}\end{split}\]

\[\begin{split}\left(\frac{2}{q}\right) = (-1)^{(q^2-1)/8} = \begin{cases} \phantom{-}1, & \text{if $q \equiv 1, 7 \pmod{8}$};\\ -1, & \text{if $q \equiv 3, 5 \pmod{8}$}. \end{cases}\end{split}\]

\[\begin{split}\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}} \left(\frac{q}{p}\right) = \begin{cases} \phantom{-}\left(\dfrac{q}{p}\right), & \text{if $p \equiv 1 \pmod{4}$ or $q \equiv 1 \pmod{4}$};\\[3ex] -\left(\dfrac{q}{p}\right), & \text{if $p \equiv 3 \pmod{4}$ and $q \equiv 3 \pmod{4}$}. \end{cases}\end{split}\]

There are many different proofs of this theorem, some are relatively simple, but still perhaps beyond the scope of these notes.

But, let’s do some computations, using Sage’s .is_square method, to reassure us that the theorem is valid.

Let’s start with he first case:

number_of_tries = 1000
min_prime = 3
max_prime = next_prime(10^6)
for _ in range(number_of_tries):
    q = random_prime(max_prime, lbound=min_prime)
    if Mod(-1, q).is_square():
        if (q % 4) == 3:
            print(f"For {q = }, we have that (-1/q) = 1, but the formula gave -1.")
            break
    else:
        if (q % 4) == 1:
            print(f"For {q = }, we have that (-1/q) = -1, but the formula gave 1.")
            break
else:  # no break
    print("It seems to work!")

It seems to work!

Now, the second case:

number_of_tries = 1000
min_prime = 3
max_prime = next_prime(10^6)
for _ in range(number_of_tries):
    q = random_prime(max_prime, lbound=min_prime)
    if Mod(2, q).is_square():
        if (q % 8) in [3, 5]:
            print(f"For {q = }, we have that (2/q) = 1, but the formula gave -1.")
            break
    else:
        if (q % 8) in [1, 7]:
            print(f"For {q = }, we have that (2/q) = -1, but the formula gave 1.")
            break
else:  # no break
    print("It seems to work!")

It seems to work!

Finally, let’s check the third case.

number_of_tries = 1000
min_prime = 3
max_prime = next_prime(10^6)
for _ in range(number_of_tries):
    q = random_prime(max_prime, lbound=min_prime)
    while True:
        p = random_prime(max_prime, lbound=min_prime)
        if p != q:
            break
    if Mod(p, q).is_square() == Mod(q, p).is_square():
        if (p % 4) == 3 and (q % 4) == 3:
            print(f"For {p = } and {q = }, should have (p/q) = (q/p), but the formula gave (p/q) = -(q/p)")
            break
    else:
        if (p % 4) == 1 or (q % 4) == 1:
            print(f"For {p = } and {q = }, should have (p/q) = -(q/p), but the formula gave (p/q) = (q/p)")
            break
else:  # no break
    print("It seems to work!")

It seems to work!

Now, let’s illustrate how we can use quadratic reciprocity to determine if an integer is a square in some $\mathbb{F}_p$:

Example 13.1

Is $-250{,}192$ a square modulo the prime $91{,}139$?

We have:

\[\begin{split}\begin{align} \left(\frac{-250192}{91139}\right) &= \left(\frac{-67914}{91139}\right) & &\text{(reduce the top modulo the bottom)}\\ &= \left(\frac{-1}{91139}\right) \cdot \left(\frac{67914}{91139}\right) & &\text{(multiplicativity of the Legendre symbol)} \\ &= (-1) \cdot \left(\frac{2 \cdot 3^2 \cdot 7^3 \cdot 11}{91139}\right) && \text{(as $91139 \equiv 4 \pmod{4}$)} \\ &= (-1) \cdot \left(\frac{2}{91339}\right) \cdot \left(\frac{3}{91139}\right)^2 \cdot \left(\frac{7}{91139}\right)^3 \cdot \left(\frac{11}{91139}\right) & &\text{(multiplicativity of the Legendre symbol)} \\ &= (-1) \cdot (-1) \cdot 1 \cdot \left(\frac{7}{91139}\right) \cdot \left(\frac{11}{91139}\right) & &\text{(as $91139 \equiv 3 \pmod{8}$ and $(\pm 1)^2 = 1$)} \\ &= -\left(\frac{91139}{7}\right) \cdot -\left(\frac{91139}{11}\right) & &\text{(as $7, 11, 91139 \equiv 3 \pmod{4}$)} \\ &= \left(\frac{6}{7}\right) \cdot \left(\frac{4}{11}\right) & &\text{(reduce top modulo bottom)} \\ &= \left(\frac{-1}{7}\right) \cdot \left(\frac{2^2}{11}\right) \\ &= (-1) \cdot \left(\frac{2}{11}\right)^2 \\ &= (-1) \cdot 1 = \boxed{-1}, \end{align}\end{split}\]

So, $-250{,}192$ is not a square modulo the $91{,}139$.

Warning

Note we had to factor a number, and this can be hard!

Of course, Sage has the Legendre symbol:

legendre_symbol(-250192, 91139)

-1

And, as observed above, it has the is_square method as well.

Mod(-250192, 91139).is_square()

False

13.2.2. Jacobi Symbol#

As the previous example illustrates, to use quadratic reciprocity to determine if an element of $\mathbb{F}_p$ is a square, we might have to factor the top number, which can be time consuming. Next, we will see how we can avoid it! We need the following generalization of the Legendre symbol:

Definition 13.4 (Jacobi Symbol)

Let $a$ and $b$ be integers with $b \geq 2$ and odd. Suppose that the prime factorization of $b$ is given by

\[b = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}.\]

Then, we define the Jacobi symbol

\[\left(\frac{a}{b}\right) = {\left(\frac{a}{p_1}\right)}^{r_1} {\left(\frac{a}{p_2}\right)}^{r_2} \cdots {\left(\frac{a}{p_k}\right)}^{r_k}.\]

(Note that the $\left(\frac{a}{p_i}\right)$ on the right are Legendre symbols.)

So, the Jacobi symbol generalizes the Legendre symbol to the case where the bottom number might be composite.

Caution

If the Jacobi symbol $\left(\frac{a}{b}\right) = 1$, it is not necessarily the case that $a$ is a square modulo $b$!

For instance:

\[\left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \cdot \left(\frac{2}{5}\right) = (-1) \cdot (-1) = 1,\]

but $2$ is not a square modulo $15$:

Mod(2, 15).is_square()

False

On the other hand, if the Jacobi symbol $\left(\frac{a}{b}\right) = -1$, it is the case that $a$ is not a square modulo $b$. And, as we shall soon see, the Jacobi symbol is still quite useful to determine if some integer is a square modulo a prime. But first, we need some basic properties:

Proposition 13.7 (Basic Properties of the Jacobi Symbol)

Let $a$, $a_1$, $a_2$, $b$, $b_1$, and $b_2$ be integers, with $b$, $b_1$, and $b_2$ odd and greater than $1$. We then have:

If $\left(\dfrac{a}{b}\right) = -1$, then $a$ is not a square modulo $b$.
If $a_1 \equiv a_2 \pmod{b}$, then $\left(\dfrac{a_1}{b}\right) = \left(\dfrac{a_2}{b}\right)$.
$\left(\dfrac{a_1a_2}{b}\right) = \left(\dfrac{a_1}{b}\right) \cdot \left(\dfrac{a_2}{b}\right)$.
$\left(\dfrac{a}{b_1b_2}\right) = \left(\dfrac{a}{b_1}\right) \cdot \left(\dfrac{a}{b_2}\right)$.

All of these are straight-forward to prove, but we will leave it to the interested reader to try to do it on their own. But, what makes it useful is the fact that Theorem 13.3 can be extended to the Jacobi symbol:

Theorem 13.4 (Quadratic Reciprocity for Jacobi Symbol)

Let $a$ and $b$ be odd integers greater than one. Then:

\[\begin{split}\left(\frac{-1}{b}\right) = (-1)^{(b-1)/2} = \begin{cases} \phantom{-}1, & \text{if $b \equiv 1 \pmod{4}$};\\ -1, & \text{if $b \equiv 3 \pmod{4}$}. \end{cases}\end{split}\]

\[\begin{split}\left(\frac{2}{b}\right) = (-1)^{(b^2-1)/8} = \begin{cases} \phantom{-}1, & \text{if $b \equiv 1, 7 \pmod{8}$};\\ -1, & \text{if $b \equiv 3, 5 \pmod{8}$}. \end{cases}\end{split}\]

\[\begin{split}\left(\frac{a}{b}\right) = (-1)^{\frac{a-1}{2} \frac{b-1}{2}} \left(\frac{b}{a}\right) = \begin{cases} \phantom{-}\left(\dfrac{b}{a}\right), & \text{if $a \equiv 1 \pmod{4}$ or $b \equiv 1 \pmod{4}$};\\[3ex] -\left(\dfrac{b}{a}\right), & \text{if $a \equiv 3 \pmod{4}$ and $b \equiv 3 \pmod{4}$}. \end{cases}\end{split}\]

Note

Note that Theorem 13.4 is exactly the same as Theorem 13.3 with all instances of $p$ replaced by $a$ and all instances of $q$ replaced by $b$.

The proof of Theorem 13.4 just requires Definition 13.4 and repeated use of Theorem 13.3, and thus is again left to the reader as an exercise.

13.2.3. Example#

Let’s illustrate how to use the Jacobi symbol to determine if a number is a square modulo a prime with an example. We take the large prime $p = 789473$:

p = 789473

Let’s see if $a = 195960$ is a square in $\mathbb{F}_p$.

a = 195960

We will use the Jacobi symbol in the process, without having to factor numbers!

On the other hand, it is important to note that since $p$ is prime, we have that the Jacobi symbol $\left(\dfrac{a}{p}\right)$ is equal to the Legendre symbol, so if we get $1$, then $a$ is a square, and if we get $-1$, then $a$ is not a square.

First, we need to remove factors of $2$ from $a$:

valuation(a, 2)

a // 2^3

Then, we have $a = 2^3 \cdot 24495$. So,

\[\left(\frac{a}{p}\right) = \left(\frac{2^3 \cdot 24495}{p}\right) = \left(\frac{2}{p}\right)^3 \cdot \left(\frac{24495}{p}\right).\]

We need to know then what is the residue of $p$ modulo $8$:

p % 8

So, we have

\[\left(\frac{a}{p}\right) = 1 \cdot \left(\frac{24495}{p}\right) = \left(\frac{24495}{p}\right).\]

We know “flip”, using Theorem 13.4, but we need to know the residues modulo $4$. But since $p \equiv 1 \pmod{8}$, we have that $p \equiv 1 \pmod{4}$.

p % 4

Tip

One can easily reduce positive numbers modulo $4$: we simply reduce the last two digits! This is true since $100$ is divisible by $4$, and hence we have

\[789473 = 789400 + 73 = 7894 \cdot 100 + 73 \equiv 7894 \cdot 0 + 73 = 73 \pmod{4}.\]

We also need to know the reduction of $p$ modulo $24495$:

p % 24495

So, we have:

\[\left(\frac{a}{p}\right) = \left(\frac{p}{24495}\right) = \left(\frac{5633}{24495}\right).\]

Important

Note that at this point we are dealing with Jacobi symbols, as we do not know if the bottom number is prime!

The new top is odd, so we can repeat the flip, checking we need to change the sign:

5633 % 4

So, we do not need to change the sign. We also need to reduce the new top modulo the new bottom:

24495 % 5633

So:

\[\left(\frac{a}{p}\right) = \left(\frac{24495}{5633}\right) = \left(\frac{1963}{5633}\right).\]

Since we already know that $5633 \equiv 1 \pmod{4}$, we can flip (with no sign change) and reduce:

5633 % 1963

This gives:

\[\left(\frac{a}{p}\right) = \left(\frac{5633}{1963}\right) = \left(\frac{1707}{1963}\right).\]

The new top is odd, so we can keep flipping:

1707 % 4

1963 % 4

So, we need to flip the sign. We also need to reduce the new top modulo the new bottom:

1963 % 1707

This gives us

\[\left(\frac{a}{p}\right) = (-1) \cdot \left(\frac{1963}{1707}\right) = (-1) \cdot \left(\frac{256}{1707}\right).\]

But now, $256 = 2^8$, and since $(\pm 1)^8 = 1$, we get:

\[\left(\frac{a}{p}\right) = (-1) \cdot \left(\frac{2^8}{1707}\right) = (-1) \cdot {\left(\frac{2}{1707}\right)}^8 = (-1) \cdot 1 = \boxed{-1}.\]

Therefore, $a = 195960$ is not a square modulo the prime $p = 789473$.

Indeed:

Mod(195960, 789473).is_square()

False

13.2.4. Algorithm#

Here is the algorithm used above to find if an integer $a$ is a square modulo a prime $p$.

Algorithm 13.1 (Quadratic Reciprocity for Square Checking)

Given an integer $a$ and an odd prime $p$, we find if $a$ is a square in $\mathbb{F}_p$.

Initialize by changing $a$ to its reduction modulo $p$.
If $a = 0$, return True.
If not, initialize the result: result = True.
While $a \neq 1$:
1. Let $k$ be the number of times that $2$ divides $a$ (i.e., k = valuation(a, 2)).
2. If $k$ is odd and $p$ is congruent to either $3$ or $5$ modulo $8$, then result = not result. (In other words, “flip” the boolean result.)
3. Set $a \leftarrow a / 2^k$.
4. If $a = 1$, return result (and we are done).
5. If both $a$ and $p$ is congruent to $3$ modulo $4$, update result = not result (for flipping).
6. Swap the values of $a$ and $p$ (e.g., a, p = p, a in Sage).
7. Reduce $a$ modulo $p$.
When the loop is done (and if we did not return the result in the body of the loop), return result.

Note

In this algorithm we basically have value $1$ of the Jacobi symbol replaced by True and the value $-1$ replaced by False. So, changing the sign (i.e., multiplying by $-1$) corresponds to the not operation of booleans.

Also note that we do not deal with negatives, since we always reduce modulo the bottom number.

Homework

You will implement this algorithm in your homework.

13.3. Square Roots Modulo Odd Primes#

13.3.1. Number of Square Roots#

We start with a definition:

Definition 13.5 (Square Roots Modulo $m$)

If element $a \in \mathbb{Z}/m\mathbb{Z}$ is square modulo $m$, i.e., if $a = b^2$ for some $b \in \mathbb{Z}/m\mathbb{Z}$, then $b$ is a square root of $a$ (in $\mathbb{Z}/m\mathbb{Z}$).

Note that the number of square roots can vary. For instance, in $\mathbb{Z}/2\mathbb{Z}$, the element $1$ has a single square root, namely $1$ itself. In $\mathbb{Z}/3\mathbb{Z}$, it has two, namely $1$ and $-1 = 2$. In $\mathbb{Z}/8\mathbb{Z}$ it has four: $1$, $3$, $5$, and $7$. But, we have:

Proposition 13.8 (Number of Square Roots Modulo Odd Primes)

If $p$ is an odd prime and $a \in \mathbb{F}_p^{\times}$ has a square root in $\mathbb{F}_p$, say $a = b^2$, then $a$ has exactly two square roots in $\mathbb{F}_p$, namely $b$ and $-b$ (or $p-b$). Moreover, $0$ has a single square root, namely, $0$ itself.

Proof. Clearly we have that $-b$ is also a square root, since

\[(-b)^2 = b^2 = a.\]

Also note that since $p \neq 2$, we have that $-b \neq b$, as if $b = -b$, then $p \mid 2b$, and so $p \mid b$. This means that $b=0$ and so $a= b^2 = 0$, but we assumed that $a \in \mathbb{F}_p^{\times}$, so $a$ cannot be zero.

For the last part, just note that if $0 = b^2$, then $p \mid b^2$, and hence $p \mid b$ (by Euclid's Lemma), i.e., $b = 0$ in $\mathbb{F}_p$.

Note that square roots in $\mathbb{F}_2$ are easy: $0$ and $1$ are their own square roots.

13.3.2. Computing Square Roots#

But now, if $p$ is an odd prime and we know that $\mathbb{F}_p^{\times}$ is a square in $\mathbb{F}_p$, i.e., $a = b^2$ for some $b \in \mathbb{F}_p$ (e.g., by using Proposition 13.3 or quadratic reciprocity), how do we find $b$?

If $p \equiv 3 \pmod{4}$, it is relatively easy: we have that $a^{(p+1)/4}$ is a square root! (Note that since $p \equiv 3 \pmod 4$, we have that $(p+1)/4$ is an integer!) Indeed, if $a = b^2$, then, using Fermat's Little Theorem

\[\left( a^{(p+1)/4} \right)^2 = a^{(p+1)/2} = \left( b^2 \right)^{(p+1)/2} = b^{p+1} = b^{2 + p-1} = b^2 \cdot b^{p-1} = a \cdot 1 = a.\]

This computation is relatively fast with Fast Powering.

If $p$ is odd and $p \not\equiv 3 \pmod{4}$, then we must have that $p \equiv 1 \pmod{4}$. In this case we use the Tonelli–Shanks algorithm:

Algorithm 13.2 (Tonelli-Shanks Algorithm)

Given a prime $p \equiv 1 \pmod{4}$ and some $a \in \mathbb{F}_p^{\times}$ that we know to be a square, then to find a square root of $a$ in $\mathbb{F}_p$ (i.e., to find $b \in \mathbb{F}_p$ such that $a=b^2$), we follow:

Initialization:
1. Find integers $h$ and $m$ such that $p-1=2^h \cdot m$, with $m$ odd. (We can use h = valuation(p - 1, 2) in Sage.)
2. Find some $c \in \mathbb{F}_p^{\times}$ that is not a square in $\mathbb{F}_p$. This can be done by taking a random elements and testing if it is a square. We can use Quadratic Reciprocity for testing. Since the odds of picking a non-square is $50\%$, we should quickly find $c$.
3. Set
\[\begin{split} \begin{align*} t &\leftarrow a^m,\\ r &\leftarrow a^{(m+1)/2}. \end{align*}\end{split}\]

(Since $m$ is odd, $(m+1)/2$ is an integer.)
Loop: while $t \neq 1$:
1. Compute the powers $t, t^2, t^4, \ldots$ (by squaring the previous!) until we get $-1$, and let $k$ be such $t^{2^{\color{red} k-1}} = -1$.
2. Update the values (in this order):

\[\begin{split}\begin{align*} d &\leftarrow \left( c^m \right)^{2^{h-k-1}}\\ t & \leftarrow d^2 \cdot t \\ r & \leftarrow d \cdot r. \end{align*}\end{split}\]

Return: $r$ (and/or $-r$).

Note

The Tonelli-Shanks algorithm also works for $p \equiv 3 \pmod{4}$, but the previous method is faster.

13.3.2.1. Why Does It Work?#

Let’s verify that the Tonelli-Shanks Algorithm works. So, let $p$ be an odd prime and $a \in \mathbb{F}_p^{\times}$ that is a square in $\mathbb{F}_p$. We then set $p-1 = 2^h \cdot m$, with $m$ odd, $t = a^m$, and $r = a^{(m+1)/2}$. If $t=1$, then using Fermat's Little Theorem, we have

\[r^2 = \left( a^{(m+1)/2} \right)^2 = a^{m+1} = a^{m} a = ta = a.\]

Hence, $r$ is a square root of $a$ as needed.

So, suppose now that $t \neq 1$. This means that $|t| \neq 1$, but what is $|t|$? Since $p-1 = 2^h \cdot m$ and using Proposition 13.3, we have that

\[t^{2^{h-1}} = (a^m)^{2^{h-1}} = a^{2^{h-1} \cdot m} = a^{(p-1)/2} = 1,\]

Hence, by Proposition 13.1, we have that $|t| \mid 2^{h-1}$, so $|t| = 2^k$ for some $0 < k \leq h-1$. We need to find this order, so we compute $t^2, (t^2)^2 = t^4, (t^4)^2 = t^8$, etc., until we get $-1$, as we know that the next power will give us $1$ (and that is the only way we can get to $1$). Hence, the power that gives $-1$ will be $t^{2^{k-1}}$.

Then, we have

\[r^2 = \left( a^{(m+1)/2} \right)^2 = a^{m+1} =a \cdot a^m = a \cdot t,\]

and so we have

(13.1)#\[\begin{split}\begin{align*} r^2 &= a \cdot t, \\ |t| &= 2^k, \quad \text{for some $1 \leq k \leq h-1$}. \end{align*}\end{split}\]

Let now $c \in \mathbb{F}_p^{\times}$ not a square and let

\[\begin{split}\begin{align*} d &= \left( c^m \right)^{2^{h - k - 1}}, \\ t' &= d^2 \cdot t, \\ r' &= d \cdot r. \end{align*}\end{split}\]

Then, we have

\[(r')^2 = d^2 \cdot r^2 = d^2 \cdot a \cdot t = (d^2 \cdot t) \cdot a = t' \cdot a.\]

Thus, it $t' = 1$, then $r'$ is a square root of $a$ as needed. Moreover, by Proposition 13.3, we have \begin{align} (t’)^{2^{k-1}} &= (d^2 \cdot t)^{2^{k-1}} = d^{2^k} \cdot t^{2^{k-1}} \ &= \left( \left( c^m \right)^{2^{h - k - 1}} \right)^{2^k} \cdot (-1) = - \left( c^m \right)^{2^{h-1}}\ &= -c^{2^{h-1}m} = -c^{(p-1)/2} = -(-1) \ &=1 \end{align} This means that $|t'| \mid 2^{k-1}$, and hence $|t'| = 2^{k'}$ for some $0 < k' < k$. So, we get a “new version” of (13.1):

\[\begin{split}\begin{align*} (r')^2 &= a \cdot t' \\ |t'| &= 2^{k'}, \quad \text{for some $1 \leq k' \leq k-1$}. \end{align*}\end{split}\]

The important thing here is that $|t'| < |t|$. If we repeat now the process, eventually we will get that the “new $t$” must have order $1$ and the corresponding $r$ is the square root of $a$.

13.3.2.2. Example#

Let’s illustrate the algorithm with an example. We will take $p = 5{,}756{,}436{,}641$.

p = 5756436641
is_prime(p)

True

Note that $p \equiv 1 \pmod{4}$:

p % 4

We have that $5$ is a square in $\mathbb{F}_p$:

a = Mod(5, p)
# a^((p-1) / 2)
a.is_square()

True

Let’s find a square root of $5$. We find $h$ and $m$, with $m$ odd, such that $p-1= 2^h \cdot m$:

h = valuation(p - 1, 2)
m = (p - 1) // 2^h

We then initialize $t$ and $r$, and check if $t = 1$:

t, r = a^m, a^((m + 1)/2)
t

5187227731

Since it is not, we have to start the loop, but before that we need to find the non-square $c$. Here I just typed a random number and checked it was not a square. If it were, I could type another one and try again, until finding a non-square.

c = Mod(573847843, p)
c.is_square()

False

Important

In practice, you would find c with something like:

c = Mod(randint(2, p-1), p)
while c.is_square():
    c = Mod(randint(2, p-1), p)

The reason that I did not do that here is because I need some control over the number of steps, which varies depending on c. So, I tried a few and found one (in just a couple of tries) to illustrate the process.

Now, we need to find $k$ such that $|t| = 2^{k}$. We do that with a simple loop:

k = 1
t_power = t  # powers of t
while t_power != Mod(-1, p):
    k += 1
    t_power ^= 2  # square previous
k

With $k$ in hand, we can get our new values:

d = (c^m)^(2^(h - k - 1))
t = d^2 * t
r = d * r

We check $t$ again.

454050411

It is still not $1$, so we repeat the process:

k = 1
t_power = t
while t_power != Mod(-1, p):
    k += 1
    t_power ^= 2

d = (c^m)^(2^(h - k - 1))
t = d^2 * t
r = d * r

t

5756436640

We need to repeat again:

k = 1
t_power = t
while t_power != Mod(-1, p):
    k += 1
    t_power ^= 2

d = (c^m)^(2^(h - k - 1))
t = d^2 * t
r = d * r

t

It is now $1$! So, r should be our square root:

629627396

Let’s check:

r^2 == a

True

13.4. Square Roots Modulo Powers of Primes#

Now we know how to find if $a$ has a square root in $\mathbb{Z}/p\mathbb{Z}$ and how to compute it if it does. How about in $\mathbb{Z}/p^n\mathbb{Z}$ for some $n > 1$? We can easily do it using Hensel’s Lemma. In fact we need only a more particular version of this powerful result, which we state below:

Theorem 13.5 (Square Roots Modulo $\mathbb{Z}/p^n\mathbb{Z}$ for $n>1$ and $p$ Odd Prime)

Let $p$ be an odd prime, $a$ an integer not divisible by $p$, and suppose that there is some integer $b_k$ such that $b_k^2 \equiv a \pmod{p^k}$ for some $k \geq 1$, i.e., $b_k$ is a square root of $a$ modulo $p^k$. Then let

\[\begin{split}\begin{align*} c_k &= \text{an inverse of $2a_k$ modulo $p^{k+1}$ (an integer)},\\ \Delta_k &= -(b_k^2 - a) \cdot c_k \text{ reduced modulo $p^{k+1}$}, \\ b_{k+1} &= b_k + \Delta_k. \end{align*}\end{split}\]

Then, $b_{k+1}^2 \equiv a \pmod{p^{k+1}}$, i.e., $b_{k+1}$ is a square root of $a$ modulo $p^{k+1}$.

Moreover, if $b^2 \equiv a \pmod{p^{k+1}}$ and $b \equiv b_k \pmod{p^k}$, then $b \equiv b_{k+1} \pmod{p^{k+1}}$, with $b_{k+1}$ obtained from $b_k$ using the procedure above.

Let’s break down what this means. First note that if $a$ has no square root modulo $p$, it cannot have a square root modulo any $p^k$ with $k \geq 1$, as if $b$ is a square root modulo $p^k$, then $p^k \mid (b^2 - a)$, which means that $p \mid (b^2 - a)$ and so this same $b$ is a square root modulo $p$ as well.

Now if $a$ does have a square root modulo $p$, say $b_1$, the theorem above tells us how to obtain a square root modulo $p^2$, say $b_2$. Then, from this square root modulo $p^2$ we can construct a square root modulo $p^3$, say $b_3$. We can iterate this process to obtain a square root of $a$ modulo any power of $p$!

We know that if $a$ has a square root modulo $p$, and $a \not\equiv 0 \pmod{p}$, then since $p$ is odd we have that $a$ has exactly two square roots modulo $p$: if $b_1$ is one of them, then $-b_1$ is the other. (Since $p \neq 2$, we have that $b_1 \not\equiv -b_1 \pmod{p}$.) So, how many square roots do we have modulo $p^2$?

Suppose that $b$ is a square root of $a$ modulo $p^2$, i.e., $p^2 \mid (b^2 - a)$. Then, clearly $p \mid (b^2 - a)$, i.e., $b$ is also a square root modulo $p$. Therefore, either $b \equiv b_1 \pmod{p}$ or $b \equiv -b_1 \pmod{p}$. The latter part of the theorem tells us that $b$ then is congruent to the square root obtained by the procedure if gives starting with the corresponding root modulo $p$. Therefore, there are only two roots modulo $p^2$: $b_2$, obtained from $b_1$ using the theorem, and the one obtained from the theorem from $-b_1$. It is not hard to see that this latter one must simply be $-b_2$.

Hence, if we iterate this process, we can see that if $a$ has a square root modulo $p$, is has exactly two square roots modulo $p^k$ for any $k \geq 1$. The following proposition summarizes this discussion:

Proposition 13.9

If $p$ is an odd prime, $a$ is an integer not divisible by $p$, and $a$ has a square root modulo $p$, then $a$ has exactly two distinct square roots modulo $p^k$ for any $k \geq 1$, with one being the negative of the other.

Let’s now prove the main theorem:

Proof. Proof of Theorem 13.5

First, note since $p \nmid a$ and $p^k \mid (b_k^2 - a)$, we have that $p \nmid b_k$.

Then, since $p$ is odd, we have that $p \nmid 2b_k$, and hence $\gcd(p^{k+1}, 2b_k) = 1$. Therefore, there is some integer $c_k$ such that

\[c_k \cdot 2b_k \equiv 1 \pmod{p^{k+1}}.\]

Then,

\[\begin{split}\begin{align*} b_{k+1}^2 &= (b_k + \Delta_k)^2 \\ &= b_k^2 + 2b_k \Delta_k + \Delta_k^2 \\ &= b_k^2 - 2b_k (b_k^2 - a)c_k + (b_k^2 - a)^2 c_k^2 \\ &\equiv b_k^2 - (b_k^2 - a) + (b_k^2 - a)^2 c_k^2 & \text{(since $c_k$ is an inverse of $2a_k$ modulo $p^{k+1}$)}\\ &\equiv a + (b_k^2 - a)^2 c_k^2 \pmod{p^{k+1}} \end{align*}\end{split}\]

Now, we know that $p^k \mid (b_k^2 - a)$, so $p^{2k} \mid (b_k^2 - a)^2$, and since $2k > k+1$ (as $k \geq 1$), we have that $p^{k+1} \mid (b_k^2 - a)$. Hence, in the expression above we get $b_{k+1}^2 \equiv a \pmod{p^{k+1}}$.

For the second part, suppose that $b^2 \equiv a \pmod{p^{k+1}}$ and $b \equiv b_k \pmod{p^k}$, where $b_k^2 \equiv a \pmod{p^k}$.

Also, using the algorithm in the first part we can construct $b_{k+1}$ such that $b_{k+1}^2 \equiv a \pmod{p^{k+1}}$. (We need to show $b \equiv b_{k+1}$.) Note that since $b_k^2 \equiv a \pmod{p^k}$, we have that $\Delta_k = -(b_k^2 -a)c_k \equiv 0 \cdot c_k = 0 \pmod{p^k}$, so $b_{k+1} = b_k + \Delta_k \equiv b_k + 0 = b_k \pmod{p^k}$.

So, we have that

\[b \equiv b_k \equiv b_{k+1} \pmod{p^k},\]

and hence, $p \mid (b - b_{k+1})$. We also have

\[b^2 \equiv a \equiv b_{k+1}^2 \pmod{p^{k+1}},\]

which means that $p^{k+1} \mid b^2 - b_{k+1}^2 = (b - b_{k+1})(b + b_{k+1})$. If $p \nmid (b + b_k)$, then we must have that $p^{k+1} \mid (b - b_{k+1})$, and we are done!

But if $p \mid (b + b_{k+1})$, since also $p \mid (b - b_{k+1})$, we have that $p$ must divide the sum $2b$. Since $p$ is odd, it must be the case that $p \mid b$. But $b \equiv b_k \not\equiv 0 \pmod{p}$, so it cannot happen.

13.4.1. Algorithm#

Let’s describe now the algorithm that given a square root $b$ of $a$ modulo an odd prime $p$ and some $n$, finds the square root of $a$ modulo $p^n$.

Algorithm 13.3 (Square Root Modulo Powers of Odd Primes)

Given an odd prime $p$, an integer $a$ not divisible by $p$, a square root of $b$ of $a$ modulo $p$, and some integer $n \geq 1$, we find a square root of $a$ modulo $p^n$:

For $k$ in $\{2, 3, 4, \ldots, n\}$, we do:
1. Set $c$ as an inverse of $2b$ modulo $p^k$.
2. Set $\Delta$ as the reduction modulo $p^k$ of $c \cdot (b^2 - a)$.
3. Set $b \leftarrow b + \Delta$.
Return $b$.

13.4.2. Example#

Let’s find a square root of $3$ in $\mathbb{Z}/13^4\mathbb{Z}$. First, we can find, with previous methods, a square root modulo $13$: $4$ is one, since $4^2 = 16 \equiv 3 \pmod{13}$. So, have $b = 4$.

a = 3
p = 13
b = 4

Now, we will be working modulo $p^2$, so we can create the $\mathbb{Z}/p^2\mathbb{Z}$ in Sage for conversions of elements:

R = Zmod(p^2)

Now, we set:

c = R(-2 * b)^(-1)
Delta = c * R(b^2 - a)
b = ZZ(R(b) + Delta)
b

If this worked, then we must have that the new $b$ is a square root modulo $p^2$:

Mod(b, p^2)^2 == Mod(a, p^2)  # b is already in Zmod(p^2)

True

Now, we repeat, with powers adjusted:

R = Zmod(p^3)
c = R(-2 * b)^(-1)
Delta = c * R(b^2 - a)
b = ZZ(R(b) + Delta)
b

And check:

b^2 == Mod(a, p^3)

True

Finally, we get to the fourth power:

R = Zmod(p^4)
c = R(-2 * b)^(-1)
Delta = c * R(b^2 - a)
b = ZZ(R(b) + Delta)
b

And the final check:

Mod(b, p^4)^2 == Mod(a, p^4)

True

Homework

You will implement this algorithm in your homework.

13.5. Square Roots Modulo Powers of $2$#

Theorem 13.5 does not apply when $p=2$. In fact, the case when $p=2$ is more complicated. But before we give the version of the theorem for $p=2$, let’s first investigate when we have square roots modulo $2^n$ and how many square roots we have.

Proposition 13.10 (Number of Square Roots Modulo $2^n$)

Let $a$ be an odd integer and $k \geq 3$.

If $a \not\equiv 1 \pmod{8}$, then there are no square roots of $a$ modulo $2^k$ (i.e., $a$ is not a square in $\mathbb{Z}/2^k\mathbb{Z}$).
If $a \equiv 1 \pmod{8}$, then there are exactly four square roots of $a$ modulo $2^k$ (in particular, $a$ is a square in $\mathbb{Z}/2^k\mathbb{Z}$).

Proof. For the first item, we have that if $b$ is square root modulo $2^k$, then it is also a square root modulo $8$ since $k \geq 3$. And we can just check by hand that $1$ is the only odd that is a square modulo $8$:

\[1^2 \equiv 3^3 \equiv 5^2 \equiv 7^2 \equiv 1 \pmod{8}.\]

We can see then that the square roots of $1$ are four: $1$, $3$, $5$, and $7$.

Now suppose that $a \equiv 1 \pmod{8}$. We must show that there is a square root modulo $2^n$. This will follow from our next result, Theorem 13.6, which does not rely on this current proposition.

So, we can now assume that there is a square root modulo $2^k$, for $k \geq 3$, and we must show that there are exactly $4$ square roots modulo $2^k$. Suppose that $x$ and $y$, with $x \neq y$, are two such square roots, i.e.,

\[x^2 \equiv a \equiv y^2 \pmod{2^k},\]

and hence $2^k \mid y^2 - x^2 = (y-x)(y+x)$.

Since $a$ is odd, we must have that $x$ and $y$ are also odd, and so $2 \mid (y-x)$ and $2 \mid (y+x)$. Since $2^k \mid (y-x)(y+x)$, together $y-x$ and $y+x$ must have $k$ factors of $2$.

Suppose the $4$ also divides both. (We will show that this cannot happen.) If so, then $4$ would also divide their sum $2y$, but that means that $y$ even, but we know it is odd. So, $4$ divides only one of between $y-x$ and $y + x$, and this one must have $k-1$ factors of $2$. Since we don’t know which, we will write that $2^{k-1} \mid y + ux$, where $u$ is either $1$ or $-1$. And, hence, we have that

\[y \equiv -ux + t 2^{k-1} \pmod{2^k}\]

where $t$ is either $0$ or $1$. This comes from the fact that $2^{k-1} \mid y + ux$, so $y + ux = s2^{k-1}$, for some integer $s$, and

\[\begin{split}s 2^{k-1} \equiv \begin{cases} 0 \pmod{2^{k}},& \text{if $s$ is even},\\ 2^{k-1} \pmod{2^{k}},& \text{if $s$ is odd}. \end{cases}\end{split}\]

Therefore, since we have two choices (modulo $2^k$) for each of $u$ ($1$ or $-1$) and $t$ ($0$ or $1$), we have four possible values for $y$ (modulo $2^k$) for a fixed square root $x$ of $a$ (which includes $x$ itself, when $u=-1$ and $t=0$), and hence we have at most four possible roots.

Note that all four possibilities do give square roots of $a$ modulo $2^k$:

\[\begin{split}\begin{align*} (-ux + t 2^{k-1})^2 &= (-ux)^2 - uxt 2^{k} + t^2 2^{2k-2} \\ &\equiv u^2 x^2 - 0 + 0 && \text{(since $2k-2 > k$, as $k \geq 3$)} \\ &\equiv x^2 && \text{(since $u$ is either $1$ or $-1$)} \\ &\equiv a \pmod{2^k} && \text{(since $x$ is a square root of $a$ modulo $2^k$)} \end{align*}\end{split}\]

Therefore, to finish the proof, we just need to show that these are all distinct modulo $2^k$. But:

For $t \in \{0, 1\}$, we have that

\[x + t2^{k-1} \not\equiv -x + t2^{k-1} \pmod{2^k},\]

since $x$ is odd (and $k \geq 3$), and so $2x \not\equiv 0 \pmod{2^k}$. (This takes care of the cases when we have the same value of $t$ for two possible solutions. So now we need to check when we have different values.)

For $u \in \{-1, 1\}$, we have that

\[ux \not\equiv ux + 2^{k-1} \pmod{2^k},\]

since $2^{k-1} \not\equiv 0 \pmod{2^k}$. (This takes care of cases when we have different values of $t$, but the same value for $u$.)

For $u \in \{-1, 1\}$, we have that

\[ux \not\equiv -ux + 2^{k-1} \pmod{2^k},\]

since $\pm 2x + 2^{k-1} \not\equiv 0 \pmod{2^k}$, since $x$ is odd. (This takes care of cases when we have different values of $t$ and $u$.)

Important

As it can be seen in the proof above, if we have one root $b$ of $a$ modulo $2^k$, then all roots are:

\[b, \qquad -b, \qquad b + 2^{k-1}, \qquad -b + 2^{k-1}.\]

Here is the equivalent version of Theorem 13.5:

Theorem 13.6 (Square Roots Modulo $\mathbb{Z}/2^n\mathbb{Z}$ for $n\geq3$)

Let $a$ an odd integer and suppose that there is some integer $b_k$ such that $b_k^2 \equiv a \pmod{2^k}$ (so $(a - b_k^2)/2^k$ is an integer) for some $k \geq 3$, i.e., $b_k$ is a square root of $a$ modulo $2^k$. Then let

\[\begin{split}\begin{align*} c_k &= (a - b_k^2)/2^k \text{ reduced modulo $2$ (so it is either $0$ or $1$)},\\ \Delta_k &= c_k \cdot 2^{k-1}, \\ b_{k+1} &= b_k + \Delta_k. \end{align*}\end{split}\]

Then, $b_{k+1}^2 \equiv a \pmod{2^{k+1}}$, i.e., $b_{k+1}$ is a square root of $a$ modulo $2^{k+1}$.

Moreover, if $b^2 \equiv a \pmod{p^{k+1}}$ and $b \equiv b_k \pmod{p^{k-1}}$, then $b \equiv b_{k+1} \pmod{2^{k}}$, with $b_{k+1}$ obtained from $b_k$ using the procedure above.

Caution

Note that the second part is weaker than for $p$ odd: as we have $b \equiv b_{k+1} \pmod{2^{\color{red} k}}$ and not modulo $2^{k+1}$.

Proof. First, note that since $2^{k-1} \mid \Delta_k$, we have that $2^{2k-2} \mid \Delta_k^2$. Since $k \geq 3$, we have that $2k-2 \geq k + 1$, and we have that $2^{k+1} \mid \Delta_k^2$. Thus

\[\begin{split}\begin{align*} b_{k+1}^2 &= (b_k + \Delta_k)^2 \\ &=b_k^2 + 2b_k \Delta_k + \Delta_k^2 \\ &\equiv b_k^2 + b_kc_k2^{k}\\ &\equiv b_k^2 + c_k2^{k} & \text{(since $b_k \equiv 1 \pmod{2}$)} \\ &= b_k^2 + a - b_k^2 = a \pmod{2^{k+1}}. \end{align*}\end{split}\]

Now suppose that $b^2 \equiv a \pmod{2^{k+1}}$ with $b \equiv b_k \pmod{2^{k-1}}$ and $b_{k+1}$ obtained from $b_{k}$ with the method above. Then, $b = b_k + t \cdot 2^{k-1}$ for some integer $t$, and hence

\[a \equiv b^2 = b_k^2 + b_k t 2^{k} \pmod{2^{k+1}}.\]

Since $b_k$ is odd, this implies that

\[a - b_k^2 \equiv b_k t 2^k \equiv t 2^k \pmod{2^{k+1}},\]

and thus

\[t \equiv \frac{a - b_k^2}{2^k} \equiv c_k \pmod{2}.\]

Hence,

\[b = b_k + t \cdot 2^{k-1} \equiv b_k + c_k 2^{k-1} = b_k + \Delta_k = b_{k+1} \pmod{2^k}.\]

13.5.1. Example#

Let’s find a square root of $a=33$ modulo $2^7$. Firstly, we might ask if such square root exist. But, since $33 \equiv 1 \pmod{8}$, by Proposition 13.10, the square root exists.

The first step is to find a root modulo $8$, and $1$, $3$, $5$, and $7$ all are. In fact, different ones might give different square roots modulo $2^7$ with the process from Theorem 13.6. Let’s use $b_3 = 3$ here in this example. (In principle we could always use $1$. But any choice between $1$, $3$, $5$, or $7$ always works.) We then have:

\[\begin{split}\begin{align*} c_3 &= \frac{33 - 3^2}{2^3} = \frac{24}{8} = 3 \equiv 1 \pmod{2} \\ \Delta_3 &= 1 \cdot 2^2 = 4 \\ b_4 &= 3 + 4 = 7. \end{align*}\end{split}\]

We then should have that $b_4$ is a square root modulo $2^4$, and indeed:

\[7^2 = 49 \equiv 33 \pmod{16}.\]

Next, we have:

\[\begin{split}\begin{align*} c_4 &= \frac{33 - 7^2}{2^4} = \frac{-16}{16} = -1 \equiv 1 \pmod{2} \\ \Delta_4 &= 1 \cdot 2^3 = 8 \\ b_5 &= 7 + 8 = 15. \end{align*}\end{split}\]

And indeed, we do have:

\[15^2 = 225 = 1 + 224 = 1 + 32 \cdot 7 \equiv 1 \equiv 33 \pmod{2^5}.\]

And, checking, we have:

\[15^2 = 225 = 33 + 3 \cdot 64 \equiv 33 \pmod{2^6}\]

And, finally:

\[\begin{split}\begin{align*} c_6 &= \frac{33 - 15^2}{2^6} = \frac{-192}{64} = -3 \equiv 1 \pmod{2} \\ \Delta_6 &= 1 \cdot 2^5 = 32 \\ b_7 &= 15 + 32 = 47. \end{align*}\end{split}\]

And, our final check:

\[47^2 = 2209 = 33 + 17 \cdot 128 \equiv 33 \pmod{2^7}.\]

So, $47$ is a square root of $33$ modulo $2^7 = 128$. The other roots are:

\[\begin{split}\begin{align*} -47 &\equiv 81 \pmod{128}, \\ 47 + 64 &\equiv 111 \pmod{128}, \\ -47 + 64 &\equiv 17 \pmod{128}. \end{align*}\end{split}\]

Caution

It is worth noting that if we started with $1$, instead of $3$, our algorithm would give the square root $17$. Starting with $5$ and $7$ would give the square roots $17$ and $47$, respectively. Therefore, the square roots $81$ and $111$ would not be obtained directly from this method. We need to find other square roots as in our last step above.

Important

We will refer to Theorem 13.5 and Theorem 13.6 collectively simply as Hensel’s Lemma, since these are simply the application of this more general result to the computation of square roots.

13.5.2. Implementation#

Here is a function that returns all square roots of a number congruent to $1$ modulo $8$ modulo a given power of $2$.

def sqrt_mod_power_2(a, n):
    """
    Given an integer a and a exponent n, returns all square roots of
    a modulo 2^n for .

    INPUTS:
    a: a integer for which we compute the square root modulo 2^n;
    n: an integer equal to 3 or larger, that is the exponent of 2 for the modulus
       of the square root.

    OUTPUT: A list containing all four square roots of a modulo 2^n in increasing
    order.  If not square root exists, returns the empty list.
    """
    #  check if square root exists
    if a % 8 != 1:
        # no square root
        return []

    b = 1  # use 1 for square root modulo 8

    # find one root
    for k in range(3, n):
        c = ((a - b^2) // 2^k) % 2
        Delta = c * 2^(k - 1)
        b += Delta

    return sorted([
        b % 2^n,
        -b % 2^n,
        (b + 2^(n - 1)) % 2^n,
        (-b + 2^(n - 1)) % 2^n,
    ])

As an example, here are the square roots we’ve computed above.

sqrt_mod_power_2(33, 7)

[17, 47, 81, 111]

Square Roots Modulo m

Contents

13. Square Roots Modulo \(m\)#

13.1. Squares Modulo Odd Primes#

13.2. Quadratic Reciprocity#

13.2.1. Legendre Symbol#

13.2.2. Jacobi Symbol#

13.2.3. Example#

13.2.4. Algorithm#

13.3. Square Roots Modulo Odd Primes#

13.3.1. Number of Square Roots#

13.3.2. Computing Square Roots#

13.3.2.1. Why Does It Work?#

13.3.2.2. Example#

13.4. Square Roots Modulo Powers of Primes#

13.4.1. Algorithm#

13.4.2. Example#

13.5. Square Roots Modulo Powers of \(2\)#

13.5.1. Example#

13.5.2. Implementation#