Given a number ‘n’ and a prime ‘p’, find square root of n under modulo p if it exists. It may be given that p is in the form for 4*i + 3 (OR p % 4 = 3) where i is an integer. Examples of such primes are 7, 11, 19, 23, 31, … etc,
Examples:
Input: n = 2, p = 7
Output: 3 or 4
Explanation: 3 and 4 both are square roots of 2 under modulo 7 because (3*3) % 7 = 2 and (4*4) % 7 = 2Input: n = 2, p = 5
Output: Square root doesn’t exist
Naive Solution: Try all numbers from 2 to p-1. And for every number x, check if x is the square root of n under modulo p.
Below is the implementation of the above approach:
C++
// A Simple C++ program to find square root under modulo p// when p is 7, 11, 19, 23, 31, ... etc,#include <iostream>using namespace std;// Returns true if square root of n under modulo p existsvoid squareRoot(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) { cout << "Square root is " << x; return; } } cout << "Square root doesn't exist";}// Driver program to testint main(){ int p = 7; int n = 2; squareRoot(n, p); return 0;} |
Java
// A Simple Java program to find square// root under modulo p when p is 7, // 11, 19, 23, 31, ... etc,import java .io.*;class GFG { // Returns true if square root of n // under modulo p exists static void squareRoot(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) { System.out.println("Square " + "root is " + x); return; } } System.out.println("Square root " + "doesn't exist"); } // Driver Code public static void main(String[] args) { int p = 7; int n = 2; squareRoot(n, p); } }// This code is contributed by Anuj_67 |
Python3
# A Simple Python program to find square # root under modulo p when p is 7, 11, # 19, 23, 31, ... etc,# Returns true if square root of n under# modulo p existsdef squareRoot(n, p): n = n % p # One by one check all numbers from # 2 to p-1 for x in range (2, p): if ((x * x) % p == n) : print( "Square root is ", x) return print( "Square root doesn't exist")# Driver program to testp = 7n = 2squareRoot(n, p)# This code is Contributed by Anuj_67 |
C#
// A Simple C# program to find square// root under modulo p when p is 7, // 11, 19, 23, 31, ... etc,using System;class GFG { // Returns true if square root of n // under modulo p exists static void squareRoot(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) { Console.Write("Square " + "root is " + x); return; } } Console.Write("Square root " + "doesn't exist"); } // Driver Code static void Main() { int p = 7; int n = 2; squareRoot(n, p); } }// This code is contributed by Anuj_67 |
PHP
<?php// A Simple PHP program to find // square root under modulo p// when p is 7, 11, 19, 23, 31, // ... etc,// Returns true if square// root of n under modulo// p existsfunction squareRoot($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) { echo("Square root is " . $x); return; } } echo("Square root doesn't exist");}// Driver Code$p = 7;$n = 2;squareRoot($n, $p);// This code is contributed by Ajit.?> |
Javascript
<script>// A Simple Javascript program to find square// root under modulo p when p is 7, // 11, 19, 23, 31, ... etc, // Returns true if square root of n // under modulo p exists function squareRoot(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) { document.write("Square " + "root is " + x); return; } } document.write("Square root " + "doesn't exist"); } // Driver Code let p = 7; let n = 2; squareRoot(n, p); // This code is contributed by rag2127 </script> |
Time Complexity: O(p)
Auxiliary Space: O(1)
Direct Method: If p is in the form of 4*i + 3, then there exist a Quick way of finding square root.
If n is in the form 4*i + 3 with i >= 1 (OR p % 4 = 3)
And
If Square root of n exists, then it must be
±n(p + 1)/4
Below is the implementation of the above idea :
C++
// An efficient C++ program to find square root under// modulo p when p is 7, 11, 19, 23, 31, ... etc.#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 square root of n under modulo p exists// Assumption: p is of the form 3*i + 4 where i >= 1void squareRoot(int n, int p){ if (p % 4 != 3) { cout << "Invalid Input"; return; } // Try "+(n^((p + 1)/4))" n = n % p; int x = power(n, (p + 1) / 4, p); if ((x * x) % p == n) { cout << "Square root is " << x; return; } // Try "-(n ^ ((p + 1)/4))" x = p - x; if ((x * x) % p == n) { cout << "Square root is " << x; return; } // If none of the above two work, then // square root doesn't exist cout << "Square root doesn't exist ";}// Driver program to testint main(){ int p = 7; int n = 2; squareRoot(n, p); return 0;} |
Java
// An efficient Java program to find square root under // modulo p when p is 7, 11, 19, 23, 31, ... etc. public 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 %2== 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 square root of n under modulo p exists // Assumption: p is of the form 3*i + 4 where i >= 1 static void squareRoot(int n, int p) { if (p % 4 != 3) { System.out.print("Invalid Input"); return; } // Try "+(n^((p + 1)/4))" n = n % p; int x = power(n, (p + 1) / 4, p); if ((x * x) % p == n) { System.out.print("Square root is " + x); return; } // Try "-(n ^ ((p + 1)/4))" x = p - x; if ((x * x) % p == n) { System.out.print("Square root is " + x); return; } // If none of the above two work, then // square root doesn't exist System.out.print("Square root doesn't exist "); } // Driver program to test static public void main(String[] args) { int p = 7; int n = 2; squareRoot(n, p); }} |
Python3
# An efficient python3 program to find square root # under modulo p when p is 7, 11, 19, 23, 31, ... etc. # 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 square root of n under# modulo p exists. Assumption: p is of the# form 3*i + 4 where i >= 1 def squareRoot(n, p): if (p % 4 != 3) : print( "Invalid Input" ) return # Try "+(n^((p + 1)/4))" n = n % p x = power(n, (p + 1) // 4, p) if ((x * x) % p == n): print( "Square root is ", x) return # Try "-(n ^ ((p + 1)/4))" x = p - x if ((x * x) % p == n): print( "Square root is ", x ) return # If none of the above two work, then # square root doesn't exist print( "Square root doesn't exist " )# Driver Codep = 7n = 2squareRoot(n, p) # This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// An efficient C# program to find square root under // modulo p when p is 7, 11, 19, 23, 31, ... etc. using System;public 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 %2 == 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 square root of n under modulo p exists // Assumption: p is of the form 3*i + 4 where i >= 1 static void squareRoot(int n, int p) { if (p % 4 != 3) { Console.Write("Invalid Input"); return; } // Try "+(n^((p + 1)/4))" n = n % p; int x = power(n, (p + 1) / 4, p); if ((x * x) % p == n) { Console.Write("Square root is " + x); return; } // Try "-(n ^ ((p + 1)/4))" x = p - x; if ((x * x) % p == n) { Console.Write("Square root is " + x); return; } // If none of the above two work, then // square root doesn't exist Console.Write("Square root doesn't exist "); } // Driver program to test static public void Main() { int p = 7; int n = 2; squareRoot(n, p); }}// This code is contributed by Ita_c. |
PHP
<?php// An efficient PHP program // to find square root under // modulo p when p is 7, 11, // 19, 23, 31, ... etc.// Utility function to do // modular exponentiation.// It returns (x^y) % p.function power($x, $y, $p){ // Initialize result $res = 1; // Update x if it // is more than or // equal to p $x = $x % $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/2 $y = $y >> 1; $x = ($x * $x) % $p; } return $res;}// Returns true if square root // of n under modulo p exists// Assumption: p is of the // form 3*i + 4 where i >= 1function squareRoot($n, $p){ if ($p % 4 != 3) { echo "Invalid Input"; return; } // Try "+(n^((p + 1)/4))" $n = $n % $p; $x = power($n, ($p + 1) / 4, $p); if (($x * $x) % $p == $n) { echo "Square root is ", $x; return; } // Try "-(n ^ ((p + 1)/4))" $x = $p - $x; if (($x * $x) % $p == $n) { echo "Square root is ", $x; return; } // If none of the above // two work, then square // root doesn't exist echo "Square root doesn't exist ";} // Driver Code $p = 7; $n = 2; squareRoot($n, $p);// This code is contributed by ajit?> |
Javascript
<script>// An efficient Javascript program to find square root under// modulo p when p is 7, 11, 19, 23, 31, ... etc. // 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 %2== 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 square root of n under modulo p exists // Assumption: p is of the form 3*i + 4 where i >= 1 function squareRoot(n, p) { if (p % 4 != 3) { document.write("Invalid Input"); return; } // Try "+(n^((p + 1)/4))" n = n % p; let x = power(n, Math.floor((p + 1) / 4), p); if ((x * x) % p == n) { document.write("Square root is " + x); return; } // Try "-(n ^ ((p + 1)/4))" x = p - x; if ((x * x) % p == n) { document.write("Square root is " + x); return; } // If none of the above two work, then // square root doesn't exist document.write("Square root doesn't exist "); } // Driver program to test let p = 7; let n = 2; squareRoot(n, p); // This code is contributed by avanitrachhadiya2155</script> |
Time Complexity: O(Log p)
Auxiliary Space: O(1)
How does this work?
We have discussed Euler’s Criterion in the previous post.
As per Euler's criterion, if square root exists, then
following condition is true
n(p-1)/2 % p = 1
Multiplying both sides with n, we get
n(p+1)/2 % p = n % p ------ (1)
Let x be the modulo square root. We can write,
(x * x) ≡ n mod p
(x * x) ≡ n(p+1)/2 [Using (1) given above]
(x * x) ≡ n(2i + 2) [Replacing n = 4*i + 3]
x ≡ ±n(i + 1) [Taking Square root of both sides]
x ≡ ±n(p + 1)/4 [Putting 4*i + 3 = p or i = (p-3)/4]
We will soon be discussing methods when p is not in above form.
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!