Modular square root

A modular square root [math]\displaystyle{ r }[/math] of an integer number [math]\displaystyle{ a }[/math] modulo an integer [math]\displaystyle{ m }[/math] greater than 1 is an integer such that:

[math]\displaystyle{ r^2 \equiv a\,\pmod m }[/math]

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 [math]\displaystyle{ m }[/math] 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 [math]\displaystyle{ m }[/math] 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 [math]\displaystyle{ a^{(m-1)/2} \bmod m }[/math] equals 1 (otherwise there is no square root if [math]\displaystyle{ a \not\equiv 0\,\pmod m }[/math]).

Modulus equal to 2

In this case the square root is congruent to the argument [math]\displaystyle{ r }[/math].

Modulus congruent to 3 modulo 4

[math]\displaystyle{ r\equiv \pm a^{(m+1)/4}\,\pmod m }[/math]

Modulus congruent to 5 modulo 8

First compute the square root of -1 ([math]\displaystyle{ i }[/math]) as follows:

[math]\displaystyle{ v\equiv (2a)^{(p-5)/8}\,\pmod m }[/math]

[math]\displaystyle{ i\equiv 2av^2\,\pmod m }[/math]

Then compute the square root as follows:

[math]\displaystyle{ r\equiv \pm av(i-1)\,\pmod m }[/math]

Modulus congruent to 1 modulo 8

In this case we can use the Shanks method.

1. Set [math]\displaystyle{ e }[/math] and an odd [math]\displaystyle{ q }[/math] such that [math]\displaystyle{ m = 2^e q+1 }[/math].
2. Choose [math]\displaystyle{ x }[/math] at random in the range [math]\displaystyle{ 1 \lt x \lt m }[/math] and set [math]\displaystyle{ z \leftarrow x^q\,\bmod m }[/math]. If [math]\displaystyle{ z^{2^{e-1}}\equiv 1\,\pmod m }[/math], repeat this step. (This generates a quadratic non-residue of [math]\displaystyle{ m }[/math].)
3. Set [math]\displaystyle{ y \leftarrow z }[/math], [math]\displaystyle{ r \leftarrow e }[/math], [math]\displaystyle{ x \leftarrow a^{(q-1)/2} \bmod m }[/math], [math]\displaystyle{ v \leftarrow ax\bmod m }[/math], [math]\displaystyle{ w \leftarrow vx \bmod m }[/math].
4. If [math]\displaystyle{ w=1 }[/math], the computation ends with [math]\displaystyle{ \pm v }[/math] as the square root.
5. Find the smallest value of [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ w^{2^k}\equiv 1\,\pmod m }[/math].
6. Set [math]\displaystyle{ d \leftarrow y^{2^{r-k-1}} \bmod m }[/math], [math]\displaystyle{ y \leftarrow d^2\,\bmod m }[/math], [math]\displaystyle{ r \leftarrow k }[/math], [math]\displaystyle{ v \leftarrow dv\,\bmod m }[/math], [math]\displaystyle{ w \leftarrow wy\,\bmod m }[/math].
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 [math]\displaystyle{ 58^{(101-1)/2} \bmod 101 = 1 }[/math] so there are two square roots to be computed.

[math]\displaystyle{ v = (2*58)^{(101-5)/8} \bmod 101 = 15^{12} \bmod 101 = 88 }[/math]

[math]\displaystyle{ i = 2*58*88^2 \bmod 101 = 10 }[/math]

Notice that [math]\displaystyle{ i*i \equiv -1 \,\pmod {101} }[/math]

[math]\displaystyle{ r = 58*88*(10-1) \bmod 101 = 82 }[/math]

So the modular square roots are 82 and its negative 19, which can be easily verified: [math]\displaystyle{ 82*82 \equiv 58 \,\pmod {101} }[/math], [math]\displaystyle{ 19*19 \equiv 58 \,\pmod {101} }[/math].

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 [math]\displaystyle{ 111^{(113-1)/2} \bmod 113 = 1 }[/math] so there are two square roots to be computed.

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

So the modular square roots are 87 and its negative 26, which can be easily verified: [math]\displaystyle{ 87*87 \equiv 111 \,\pmod {113} }[/math], [math]\displaystyle{ 26*26 \equiv 111 \,\pmod {113} }[/math].