Given a number ‘n’ and a prime p, find if square root of n under modulo p exists or not. A number x is square root of n under modulo p if (x*x)%p = n%p.
Examples :
Input: n = 2, p = 5 Output: false There doesn't exist a number x such that (x*x)%5 is 2 Input: n = 2, p = 7 Output: true There exists a number x such that (x*x)%7 is 2. The number is 3.
A Naive Method is to try every number x where x varies from 2 to p-1. For every x, check if (x * x) % p is equal to n % p.
C++
// A Simple C++ program to check if square root of a number// under modulo p exists or not#include<iostream>using namespace std;// Returns true if square root of n under modulo p existsbool squareRootExists(int n, int p){ n = n%p; // One by one check all numbers from 2 to p-1 for (int x=2; x<p; x++) if ((x*x)%p == n) return true; return false;}// Driver program to testint main(){ int p = 7; int n = 2; squareRootExists(n, p)? cout << "Yes": cout << "No"; return 0;} |
Java
// A Simple Java program to check if square // root of a number under modulo p exists or notimport java.util.*;class GFG { // Returns true if square root of n under // modulo p exists static boolean squareRootExists(int n, int p) { n = n % p; // One by one check all numbers from 2 // to p-1 for (int x = 2; x < p; x++) if ((x * x) % p == n) return true; return false; } // Driver program to test public static void main (String[] args) { int p = 7; int n = 2; if(squareRootExists(n, p)) System.out.print("Yes"); else System.out.print("No"); }}// This code is contributed by Anant Agarwal. |
Python3
# A Simple Python 3 program to # check if square root of a number# under modulo p exists or not# Returns true if square root of# n under modulo p existsdef squareRootExists(n, p): n = n % p # One by one check all numbers # from 2 to p-1 for x in range(2, p, 1): if ((x * x) % p == n): return True return False# Driver Codeif __name__ == '__main__': p = 7 n = 2 if(squareRootExists(n, p) == True): print("Yes") else: print("No")# This code is contributed by# Surendra_Gangwar |
C#
// A Simple C# program to check// if square root of a number // under modulo p exists or notusing System;class GFG{ // Returns true if square root of // n under modulo p exists static bool squareRootExists(int n, int p) { n = n % p; // One by one check all numbers // from 2 to p-1 for (int x = 2; x < p; x++) if ((x * x) % p == n) return true; return false; } // Driver code public static void Main () { int p = 7; int n = 2; if(squareRootExists(n, p)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by Sam007. |
PHP
<?php// A Simple PHP program to check // if square root of a number// under modulo p exists or not// Returns true if square root // of n under modulo p existsfunction squareRootExists($n, $p){ $n = $n % $p; // One by one check all // numbers from 2 to p-1 for ($x = 2; $x < $p; $x++) if (($x * $x) % $p == $n) return true; return false;}// Driver Code$p = 7;$n = 2;if(squareRootExists($n, $p) == true) echo "Yes";else echo "No";// This code is contributed by ajit?> |
Javascript
<script>// A Simple Javascript program to check// if square root of a number// under modulo p exists or not// Returns true if square root// of n under modulo p existsfunction squareRootExists(n, p){ n = n % p; // One by one check all // numbers from 2 to p-1 for(let x = 2; x < p; x++) if ((x * x) % p == n) return true; return false;}// Driver Codelet p = 7;let n = 2;if (squareRootExists(n, p) === true) document.write("Yes");else document.write("No");// This code is contributed by _saurabh_jaiswal</script> |
Output :
Yes
Time Complexity of this method is O(p).
Space Complexity: O(1) since only constant variables being used
This problem has a direct solution based on Euler’s Criterion.
Euler’s criterion states that
Square root of n under modulo p exists if and only if n(p-1)/2 % p = 1 Here square root of n exists means is, there exist an integer x such that (x * x) % p = 1
Below is implementation based on above criterion. Refer Modular Exponentiation for power function.
C++
// C++ program to check if square root of a number// under modulo p exists or not#include<iostream>using namespace std;// Utility function to do modular exponentiation.// It returns (x^y) % p.int power(int x, int y, int p){ int res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res;}// Returns true if there exists an integer x such // that (x*x)%p = n%pbool squareRootExists(int n, int p){ // Check for Euler's criterion that is // [n ^ ((p-1)/2)] % p is 1 or not. if (power(n, (p-1)/2, p) == 1) return true; return false;}// Driver program to testint main(){ int p = 7; int n = 2; squareRootExists(n, p)? cout << "Yes": cout << "No"; return 0;} |
Java
// Java program to check if// square root of a number// under modulo p exists or notimport java.io.*;class GFG{ // Utility function to do// modular exponentiation.// It returns (x^y) % p.static int power(int x, int y, int p){ int res = 1; // Initialize result x = x % p; // Update x if it is more // than or equal to p while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) == 0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Returns true if there// exists an integer x such // that (x*x)%p = n%pstatic boolean squareRootExists(int n, int p){ // Check for Euler's criterion // that is [n ^ ((p-1)/2)] % p // is 1 or not. if (power(n, (p - 1) / 2, p) == 1) return true; return false;}// Driver Codepublic static void main (String[] args) { int p = 7; int n = 2; if(squareRootExists(n, p)) System.out.println ("Yes"); else System.out.println("No");}}// This code is contributed by ajit |
Python3
# Python3 program to check if square root # of a number under modulo p exists or not# Utility function to do modular # exponentiation. It returns (x^y) % p.def power(x, y, p): res = 1 # Initialize result x = x % p # Update x if it is more than # or equal to p while (y > 0): # If y is odd, multiply # x with result if (y & 1): res = (res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (x * x) % p return res# Returns true if there exists an integer# x such that (x*x)%p = n%pdef squareRootExists(n, p): # Check for Euler's criterion that is # [n ^ ((p-1)/2)] % p is 1 or not. if (power(n, (int)((p - 1) / 2), p) == 1): return True return False# Driver Codep = 7n = 2if(squareRootExists(n, p) == True): print("Yes")else: print("No")# This code is contributed by Rajput-Ji |
C#
// C# program to check if// square root of a number// under modulo p exists or notusing System;class GFG{ // Utility function to do// modular exponentiation.// It returns (x^y) % p.static int power(int x, int y, int p){ int res = 1;// Initialize result x = x % p; // Update x if it is more // than or equal to p while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) == 0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Returns true if there// exists an integer x such // that (x*x)%p = n%pstatic bool squareRootExists(int n, int p){ // Check for Euler's criterion // that is [n ^ ((p-1)/2)] % p // is 1 or not. if (power(n, (p - 1) / 2, p) == 1) return true; return false;}// Driver Codestatic public void Main (){ int p = 7; int n = 2; if(squareRootExists(n, p)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by m_kit |
PHP
<?php// PHP program to check // if square root of a // number under modulo // p exists or not// Utility function to // do modular exponentiation // It returns (x^y) % p.function power($x, $y, $p){ $res = 1; // Initialize result $x = $x % $p; // Update x if it // is more than // or equal to p while ($y > 0) { // If y is odd, multiply // x with result if ($y & 1) $res = ($res * $x) % $p; // y must be even now $y = $y >> 1; // y = y/2 $x = ($x * $x) % $p; } return $res;}// Returns true if there // exists an integer x such // that (x*x)%p = n%pfunction squareRootExists($n, $p){ // Check for Euler's criterion // that is [n ^ ((p-1)/2)] % p // is 1 or not. if (power($n, (int)(($p - 1) / 2), $p) == 1) return true; return false;}// Driver Code$p = 7;$n = 2;if(squareRootExists($n, $p) == true) echo "Yes";else echo "No";// This code is contributed by ajit?> |
Javascript
<script> // Javascript program to check if // square root of a number // under modulo p exists or not // Utility function to do // modular exponentiation. // It returns (x^y) % p. function power(x, y, p) { let res = 1;// Initialize result x = x % p; // Update x if it is more // than or equal to p while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) == 0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Returns true if there // exists an integer x such // that (x*x)%p = n%p function squareRootExists(n, p) { // Check for Euler's criterion // that is [n ^ ((p-1)/2)] % p // is 1 or not. if (power(n, (p - 1) / 2, p) == 1) return true; return false; } let p = 7; let n = 2; if(squareRootExists(n, p)) document.write("Yes"); else document.write("No");</script> |
Output :
Yes
How does this work?
If p is a prime, then it must be an odd number and (p-1)
must be an even, i.e., (p-1)/2 must be an integer.
Suppose a square root of n under modulo p exists, then
there must exist an integer x such that,
x2 % p = n % p
or,
x2 ? n mod p
Raising both sides to power (p-1)/2,
(x2)(p-1)/2 ? n(p-1)/2 mod p
xp-1 ? n(p-1)/2 mod p
Since p is a prime, from Fermat's theorem, we can say that
xp-1 ? 1 mod p
Therefore,
n(p-1)/2 ? 1 mod p
Time Complexity: O(logp)
Auxiliary Space: O(1)
You may like to see below:
Find Square Root under Modulo p | Set 1 (When p is in form of 4*i + 3)
This article is contributed by Shivam Gupta. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
