Modular square root

A modular square root $r$ of an integer number $a$ modulo an integer $m$ greater than 1 is an integer such that:

$r^2\equiv a(\mathrm{mod}m)$

In this article we will consider the case when the modulus is prime. Otherwise we can compute the square roots modulo the prime factors of $m$ and then generate a solution using the Chinese Remainder Theorem.

When the argument is congruent to zero, there is only one modular square root, namely zero. Otherwise, the number of square roots can be two or zero depending on whether the argument is a quadratic residue modulo $m$ or not. The sum of both square roots is congruent to zero.

In order to compute the square root, we will consider different cases, depending on the modulus. When this modulus is odd, we assume that the quantity $a^{(m-1)/2}modm$ equals 1 (otherwise there is no square root if $a\not\equiv 0(\mathrm{mod}m)$).

Modulus equal to 2

In this case the square root is congruent to the argument $r$.

Modulus congruent to 3 modulo 4

$r\equiv \pm a^{(m+1)/4}(\mathrm{mod}m)$

Modulus congruent to 5 modulo 8

First compute the square root of -1 ($i$) as follows:

$v\equiv (2a{)}^{(p-5)/8}(\mathrm{mod}m)$

$i\equiv 2a{v}^2(\mathrm{mod}m)$

Then compute the square root as follows:

$r\equiv \pm av(i-1)(\mathrm{mod}m)$

Modulus congruent to 1 modulo 8

In this case we can use the Shanks method.

1. Set $e$ and an odd $q$ such that $m=2^{e}q+1$.
2. Choose $x$ at random in the range $1<x<m$ and set $z\leftarrow x^{q}modm$. If $z^{2^{e-1}}\equiv 1(\mathrm{mod}m)$, repeat this step. (This generates a quadratic non-residue of $m$.)
3. Set $y\leftarrow z$, $r\leftarrow e$, $x\leftarrow a^{(q-1)/2}modm$, $v\leftarrow axmodm$, $w\leftarrow vxmodm$.
4. If $w=1$, the computation ends with $\pm v$ as the square root.
5. Find the smallest value of $k$ such that $w^{2^k}\equiv 1(\mathrm{mod}m)$.
6. Set $d\leftarrow y^{2^{r-k-1}}modm$, $y\leftarrow d^{2}modm$, $r\leftarrow k$, $v\leftarrow dvmodm$, $w\leftarrow wymodm$.
7. Go to step 4.

Example 1

Find the square root of 58 modulo 101.

First of all we check that the modulus 101 is prime. Then we find that it is congruent to 5 mod 8.

Now we compute ${58}^{(101-1)/2}mod101=1$ so there are two square roots to be computed.

$v=(2\ast 58{)}^{(101-5)/8}mod101={15}^{12}mod101=88$

$i=2\ast 58\ast {88}^{2}mod101=10$

Notice that $i\ast i\equiv -1(\mathrm{mod}101)$

$r=58\ast 88\ast (10-1)mod101=82$

So the modular square roots are 82 and its negative 19, which can be easily verified: $82\ast 82\equiv 58(\mathrm{mod}101)$, $19\ast 19\equiv 58(\mathrm{mod}101)$.

Example 2

Find the square root of 111 modulo 113.

First of all we check that the modulus 113 is prime. Then we find that it is congruent to 1 mod 8.

Now we compute ${111}^{(113-1)/2}mod113=1$ so there are two square roots to be computed.

• Step 1: $e=4$, $q=7$.
• Step 2: $x=2$, $z=2^{7}mod113=15$, $z^{2^3}mod113=1$, so we have to repeat step 2.
• Step 2: $x=3$, $z=3^{7}mod113=40$, $z^{2^3}mod113=112$.
• Step 3: $y=40$, $r=4$, $x={111}^{(7-1)/2}mod113=105$, $v=111\ast 105mod113=16$, $w=16\ast 105mod113=98$.
• Step 4: $w$ is not equal to 1 so the computation continues.
• Step 5: $k=2$
• Step 6: $d={40}^{2^{4-2-1}}mod113=18$, $y={18}^{2}mod113=98$, $r=2$, $v=18\ast 16mod113=62$, $w=98\ast 98mod113=112$.
• Step 4: $w$ is not equal to 1 so the computation continues.
• Step 5: $k=1$
• Step 6: $d={98}^{2^{2-1-1}}mod113=98$, $y={98}^{2}mod113=112$, $r=1$, $v=98\ast 62mod113=87$, $w=112\ast 112mod113=1$.
• Step 4: $w=1$, so the square root is $\pm v=\pm 87$.

So the modular square roots are 87 and its negative 26, which can be easily verified: $87\ast 87\equiv 111(\mathrm{mod}113)$, $26\ast 26\equiv 111(\mathrm{mod}113)$.