Euler’s criterion (Check if square root under modulo p exists)
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 exists 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 program to test int 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 not import 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 exists def 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 Code if __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 not using 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 exists function 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 exists function 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 Code let 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%p 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 program to test int 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 not import 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%p static 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 Code public 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%p def 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 ): 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 not using 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%p static 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 Code static 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%p function 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)
Contact Us