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