# Modular square root

### From Mersennewiki

A **modular square root** of an integer number modulo an integer greater than 1 is an integer such that:

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 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 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 equals 1 (otherwise there is no square root if ).

## Contents |

### Modulus equal to 2

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

### Modulus congruent to 3 modulo 4

### Modulus congruent to 5 modulo 8

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

Then compute the square root as follows:

### Modulus congruent to 1 modulo 8

In this case we can use the Shanks method.

- Set and an odd such that .
- Choose at random in the range and set . If , repeat this step. (This generates a quadratic non-residue of .)
- Set , , , , .
- If , the computation ends with as the square root.
- Find the smallest value of such that .
- Set , , , , .
- 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 so there are two square roots to be computed.

Notice that

So the modular square roots are 82 and its negative 19, which can be easily verified: , .

### 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 so there are two square roots to be computed.

- Step 1: , .
- Step 2: , , , so we have to repeat step 2.
- Step 2: , , .
- Step 3: , , , , .
- Step 4: is not equal to 1 so the computation continues.
- Step 5:
- Step 6: , , , , .
- Step 4: is not equal to 1 so the computation continues.
- Step 5:
- Step 6: , , , , .
- Step 4: , so the square root is .

So the modular square roots are 87 and its negative 26, which can be easily verified: , .