Dado un número ‘n’ y un primo ‘p’, encuentre la raíz cuadrada de n bajo módulo p si existe. Se puede dar que p está en la forma de 4*i + 3 (O p % 4 = 3) donde i es un número entero. Ejemplos de tales números primos son 7, 11, 19, 23, 31, … etc.
Ejemplos:
Input: n = 2, p = 7 Output: 3 or 4 3 and 4 both are square roots of 2 under modulo 7 because (3*3) % 7 = 2 and (4*4) % 7 = 2 Input: n = 2, p = 5 Output: Square root doesn't exist
Solución ingenua: pruebe todos los números del 2 al p-1. Y para cada número x, compruebe si x es la raíz cuadrada de n en el módulo p.
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 exists
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) {
cout << "Square root is " << x;
return;
}
}
cout << "Square root doesn't exist";
}
// Driver program to test
int 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 exists def 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 test p = 7 n = 2 squareRoot(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 exists
function 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>
Producción:
Square root is 3
La complejidad temporal de esta solución es O(p)
Método directo: si p tiene la forma de 4*i + 3, entonces existe una forma rápida de encontrar la raíz cuadrada.
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
A continuación se muestra la implementación de la idea anterior:
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 >= 1
void 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 test
int 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 Code p = 7 n = 2 squareRoot(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 >= 1
function 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>
Producción:
Square root is 4
La complejidad temporal de esta solución es O(Log p)
¿Cómo funciona esto?
Hemos discutido el Criterio de Euler en la publicación anterior.
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]
Pronto discutiremos métodos cuando p no está en la forma anterior.
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