Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Modular Square Root
2.1.
Modulus equal to 2
2.2.
Modulus congruent to 3 modulo 4
2.3.
Modulus congruent to 5 modulo 8
2.4.
Tonelli-Shank's algorithm to find a square root modulo prime
2.5.
Example
3.
Uses of Modular Square Roots
4.
Frequently Asked Questions
4.1.
Can you take the square root in modular arithmetic?
4.2.
What is modular arithmetic used for?
4.3.
What is the difference between modular arithmetic and regular arithmetic?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

What is Square Roots Modulo?

Author Sanjana Yadav
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

What is Square Roots Modulo?

So, let’s get started!

Modular Square Root

In mathematics, the square root of a number x is a number y such that y2 = 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:

y2 x (mod p)

In other words, it is a number y such that y2 is congruent to x (mod p), where "congruent" means that the difference between y2 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 y2  9 (mod 7). We find that y = 3 satisfies this equation because 32  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 2xu2 (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 y2 = 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 = zt, and set x = a((t + 1)/2).
  5. For i = 1 to q - 1:
    1. Set b = y2
    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) = 152 (mod 101)= 88
  2. j= 2*58*882 (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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Uses of Modular Square Roots

Modular square roots are used in a variety of applications, including

  1. Cryptography: Modular square roots are used in some cryptographic algorithms to perform operations on large integers. For example, the RSA algorithm uses modular square roots to encrypt and decrypt messages.
  2. Error-correcting codes: Modular square roots can be used to design and implement error-correcting codes, which are used to detect and correct errors in transmitted data.
  3. Data compression: Modular square roots can be used to compress data by representing large integers as smaller numbers modulo a prime.
  4. Number theory: Modular square roots are used in number theory to study the properties of integers and their relationships to each other.
  5. Computing: Modular square roots can be used in algorithms for efficiently computing large integer operations, such as multiplication and division.
  6. Science and engineering: Modular square roots are used in various scientific and engineering applications, such as solving equations and modeling physical systems.

Frequently Asked Questions

Can you take the square root in modular arithmetic?

Yes. If an integer has a square modulo a prime, then that square modulo that prime has a square root.

What is modular arithmetic used for?

Many applications of modular arithmetic may be found in cryptography and computer programming. It is frequently used to identify errors in identification numbers.

What is the difference between modular arithmetic and regular arithmetic?

Modular arithmetic is nearly identical to whole-number arithmetic. The primary distinction is that operations require remainders after division by a defined number (the modulus) rather than integers.

Conclusion

In this article, we learned about Modular Square Roots. We saw what they are, how we find them, Tonelli-Shank's algorithm, and examples to understand them better. We also looked at their various uses.

 

We hope this article has clarified your understanding of Square Roots Modulo. You can refer to our blogs to understand more about cryptographic concepts.

 

You can also visit our website to read more such blogs. Make sure you enroll in our courses, take mock tests, solve problems, and interview puzzles. Also, you can prepare for interviews with interview experiences and an interview bundle.

Keep learning and keep growing, Ninjas!

Thank you
Previous article
Introduction to the Miller-Rabin Algorithm
Next article
What are Factoring Algorithms?
Live masterclass