What is Square Roots Modulo?

Introduction

Hello Reader!!

In this article, we will learn about Modular square roots. We will see what they are, how we find them, Tonelli-Shank's algorithm, and examples to understand them better. We will also see their various uses.

So, let’s get started!

Modular Square Root

In mathematics, the square root of a number x is a number y such that y² = x. For example, the square root of 9 is 3 because 3^2 = 9.

The square root of a number x modulo a prime number p is a number y such that:

y² x (mod p)

In other words, it is a number y such that y² is congruent to x (mod p), where "congruent" means that the difference between y² and x is divisible by p.

For example, we want to find the square root of 9 modulo 7. We can start by trying different values of y and see if they satisfy the equation y²  9 (mod 7). We find that y = 3 satisfies this equation because 3²  9 (mod 7). Therefore, the square root of 9 modulo 7 is 3.

It is important to note that the square root of a number x modulo a prime number p may not be unique. For example, the square root of 9 modulo 7 is 3, but -3 is also a square root of 9 modulo 7 because (-3)²   9 (mod 7).

Here, we will look at the scenario where we have a prime modulus. Alternatively, we can compute the square roots modulo the prime components of p and then find a solution using the Chinese Remainder Theorem.

If the argument is congruent to zero, there is only 1 modular square root, which is zero. Conversely, depending on whether the input is a quadratic residue modulo p or not, the number of square roots might be either two or zero. Both square roots added together congruently equal zero.

In accordance with the modulus, we will consider several possibilities to compute the square root. If this modulus is odd, then we'll presume the value x^((p-1)/2) mod p is 1.

Modulus equal to 2

In this instance, the square root is congruent to the argument y.

Modulus congruent to 3 modulo 4

y x^((p+1)/4) (mod p)

Modulus congruent to 5 modulo 8

To begin, we first compute the square root of -1 (j) as follows:

u (2x)^(m-5)/8 (mod p)

j 2xu² (mod p)

Now, finding the square root

y xu^(j-1) (mod p)

Tonelli-Shank's algorithm to find a square root modulo prime

Shank's method, also known as the Tonelli-Shank's algorithm, is an efficient method for finding a square root modulo a prime number. It is an extension of the classical Tonelli-Shank's algorithm, which finds the square root of a number modulo a composite number.

Here's how Shank's method works:

1. Given a prime number p and a quadratic residue x modulo p, we want to find a square root y such that y² = x (mod p).
2. Let q be a prime divisor of p - 1, and let t be a positive integer such that (p - 1)/q is odd.
3. Find a non-quadratic residue z such that z^{((p - 1)/q)} is not equal to 1 (mod p).
4. Set c = z^t, and set x = a^{((t + 1)/2)}.
5. For i = 1 to q - 1:
   1. Set b = y²
   2. If b = x (mod p), then return x as the square root of a modulo p.
   3. Otherwise, set y = (y * c) mod p
6. If the algorithm has not returned a value, then no square root of x modulo p exists.

Shank's method has a running time of O(q * log p), which is faster than the naive approach of testing all possible values of x in the range 0 to p - 1.

Let us now solve an example to get a better understanding.

Example

Finding the Square root of 58 modulo 101

We first verify that 101 is a prime number. 

Then, we observe that it is congruent to 5 mod 8.

Computing, 58^((101-1)/2) (mod 101) = 1. Two square roots exist.

1. u=(2*58)^((101-5)/8) (mod 101) = 15² (mod 101)= 88
2. j= 2*58*88² (mod 101) = 10
3. Note that j*j = -1 (mod 101)
4. y= 58*88*(10-1) (mod 101) = 82

Therefore, the square roots of 58 modulo 101 are 82, and it's negative, i.e., 19.