Dado un número ‘n’ y un primo p, encuentre si la raíz cuadrada de n bajo el módulo p existe o no. Un número x es raíz cuadrada de n bajo módulo p si (x*x)%p = n%p.
Ejemplos:
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.
Un método ingenuo es probar cada número x donde x varía de 2 a p-1. Para cada x, compruebe si (x * x) % p es igual a 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 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>
Producción :
Yes
La complejidad temporal de este método es O(p).
Complejidad espacial : O (1) ya que solo se utilizan variables constantes
Este problema tiene una solución directa basada en el Criterio de Euler.
El criterio de Euler establece que
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
A continuación se muestra la implementación basada en el criterio anterior. Consulte Exponenciación modular para la función de potencia.
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>
Producción :
Yes
¿Como funciona esto?
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 Fermet's theorem, we can say that xp-1 ? 1 mod p Therefore, n(p-1)/2 ? 1 mod p
Complejidad de tiempo: O (logp)
Espacio auxiliar: O(1)
Puede que le guste ver a continuación:
Buscar raíz cuadrada en Modulo p | Conjunto 1 (cuando p está en forma de 4*i + 3)
Este artículo es una contribución de Shivam Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA