Dado un número entero N y un número entero P que denotan el producto de dos números primos, la tarea es encontrar todas las raíces cuadradas posibles de N bajo el módulo P si existe. Se da que P es el producto de p1 y p2 , donde p1 y p2 son números primos de la forma 4i + 3 donde i es cualquier número entero. Algunos ejemplos de tales números primos son (7, 11, 19, 23, 31).
Ejemplos:
Entrada: N = 67, P = 77
Salida: 23 65 12 54
Explicación:
Todas las respuestas posibles son (23, 65, 12, 54)
Entrada: N = 188, P = 437
Salida: 25 44 393 412
Explicación:
Todas las respuestas posibles son (25, 44, 393, 412)
Enfoque ingenuo:
el enfoque más simple para resolver este problema es considerar todos los números de 2 a P – 1 y, para cada número, verificar si es la raíz cuadrada de N bajo el módulo P. Si se encuentra que es cierto, imprima ese número y rompa.
Tiempo Complejidad: O(P)
Espacio Auxiliar: O(1)
Enfoque Eficiente:
Para optimizar el enfoque anterior, la idea es usar la factorización prima para obtener dos factores p1 y p2 y luego encontrar la raíz cuadrada de ambos usando la raíz cuadrada bajo mod P . Luego usa el teorema chino del residuo para encontrar elraíz cuadrada módulo p1 * p2 . Cada conjunto contendrá dos ecuaciones (ya que hay dos raíces cuadradas cada una para módulo p1 y p2 ). Combinándolos todos, se obtienen cuatro conjuntos de ecuaciones que dan las cuatro respuestas posibles.
Siga los pasos a continuación para resolver este problema:
- Factoriza el número P usando la factorización prima. Los factores serán dos primos p1 y p2 .
- Encuentre los números primos de raíz cuadrada módulo p1 y p2 .
- Se encuentran dos conjuntos de respuestas, uno para cada número primo. Cada conjunto contiene dos números.
- Entonces habrá 4 conjuntos de ecuaciones si se elige un número de cada conjunto.
- Realice el teorema chino del resto para encontrar el módulo de raíz cuadrada p1 * p2 e imprímalos.
A continuación se muestra la implementación del enfoque anterior donde se usa la clase BigInteger en Java para manejar números muy grandes:
Java
// Java program for the above approach
import java.math.*;
import java.util.*;
class SqrtMod {
// Function to find the modulo inverse
// of a with respect to m
static BigInteger modInverse(BigInteger a,
BigInteger m)
{
BigInteger m0 = m;
BigInteger y = new BigInteger("0"),
x = new BigInteger("1");
if (m.compareTo(new BigInteger("1")) == 0)
return new BigInteger("0");
// Perform Extended Euclid Algorithm
while (a.compareTo(new BigInteger("1")) > 0) {
if (m.toString().equals("0"))
break;
BigInteger q = a.divide(m);
BigInteger t = m;
// M is remainder now, process
// Extended Euclid Algorithm
m = a.mod(m);
a = t;
t = y;
y = x.subtract(q.multiply(y));
x = t;
}
// Make x positive
while (x.compareTo(new BigInteger("0")) < 0)
x = x.add(m0);
return x;
}
// Function to apply the Chinese
// Remainder Theorem
static String CRT(BigInteger num[],
BigInteger rem[],
int k)
{
BigInteger prod = new BigInteger("1");
// Find product of all numbers
for (int i = 0; i < k; i++)
prod = prod.multiply(num[i]);
BigInteger result = new BigInteger("0");
// Apply the above formula
for (int i = 0; i < k; i++) {
BigInteger pp = prod.divide(num[i]);
result = result.add(rem[i]
.multiply(modInverse(pp,
num[i]))
.multiply(pp));
}
// Return result
return result.mod(prod).toString();
}
// Function to perform modular
// exponentiation
static BigInteger powMod(BigInteger base1,
BigInteger exponent,
BigInteger modulus)
{
BigInteger result = new BigInteger("1");
base1 = base1.mod(modulus);
while (exponent
.compareTo(new BigInteger("0"))
> 0) {
if (exponent
.mod(new BigInteger("2"))
.equals(new BigInteger("1")))
result = (result.multiply(base1))
.mod(modulus);
exponent = exponent
.divide(new BigInteger("2"));
base1 = base1
.multiply(base1)
.mod(modulus);
}
// Return the result
return result;
}
// Function that returns square root
// of n under modulo p if exists
static BigInteger squareRoot(
BigInteger n,
BigInteger p)
{
// For Invalid Input
if (!p.mod(new BigInteger("4"))
.equals(new BigInteger("3"))) {
System.out.print("Invalid Input");
return new BigInteger("-1");
}
n = n.mod(p);
// Try "+(n^((p + 1)/4))"
BigInteger x = powMod(n,
(p.add(new BigInteger("1")))
.divide(new BigInteger("4")),
p);
if ((x.multiply(x)).mod(p).equals(n)) {
return x;
}
// Try "-(n ^ ((p + 1)/4))"
x = p.subtract(x);
if ((x.multiply(x)).mod(p).equals(n)) {
return x;
}
// If none of above two work,
// then sqrt doesn't exist
return new BigInteger("-1");
}
// Function to find the ceiling
// of square root of a number
public static BigInteger
sqrtC(BigInteger x)
{
// If number < zero
if (x.compareTo(BigInteger.ZERO) < 0) {
return new BigInteger("-1");
}
// If number is zero or 1
if (x == BigInteger.ZERO
|| x == BigInteger.ONE) {
return x;
}
BigInteger two
= BigInteger.valueOf(2L);
BigInteger y;
// Iterate to find the square root
for (y = x.divide(two);
y.compareTo(x.divide(y)) > 0;
y = ((x.divide(y)).add(y)).divide(two))
;
if (x.compareTo(y.multiply(y)) == 0) {
return y;
}
else {
return y.add(BigInteger.ONE);
}
}
// Function to factorise number P
static BigInteger[] factorise(BigInteger p)
{
BigInteger ans[] = new BigInteger[2];
BigInteger b = new BigInteger("2");
BigInteger ONE = new BigInteger("1");
BigInteger ZERO = new BigInteger("0");
// Iterate over [2, sqrt(N)]
for (; b.compareTo(
sqrtC(p).add(ONE))
< 0;
b = b.add(ONE)) {
// Check if mod is zero
if (p.mod(b).equals(ZERO)) {
ans[0] = b;
ans[1] = p.divide(b);
}
}
// Return the ans
return ans;
}
// Function to find the all possible
// squareRoot of a under modulo m
public static void
solve(BigInteger a, BigInteger m)
{
// Find factorization of m
BigInteger s[] = factorise(m);
BigInteger ZERO = new BigInteger("0");
// If number P is not product
// of two primes
if (!s[0].multiply(s[1]).equals(m)) {
System.out.println("Not a product "
+ "of two primes");
}
// Find the numbers
else {
BigInteger s1[] = new BigInteger[4];
BigInteger a1[] = new BigInteger[4];
BigInteger a2[] = new BigInteger[2];
// Find squareRoot
a1[0] = squareRoot(a.mod(s[0]), s[0]);
a1[1] = squareRoot(a.mod(s[1]), s[1]);
a1[2] = a1[0].multiply(new BigInteger("-1"));
a1[3] = a1[1].multiply(new BigInteger("-1"));
// Compare to Zero
while (a1[2].compareTo(ZERO) < 0)
a1[2] = a1[2].add(s[0]);
while (a1[3].compareTo(ZERO) < 0)
a1[3] = a1[3].add(s[1]);
s1[0] = s[0];
s1[1] = s[1];
s1[2] = s[0];
s1[3] = s[1];
// Condition for no solution
if (a1[0].equals(new BigInteger("-1"))
|| a1[1].equals(new BigInteger("-1"))) {
System.out.println("No Solution");
}
// Else print all possible answers
else {
// Perform Chinese Remainder
// Theorem and print numbers
System.out.print(
CRT(s, a1, 2) + " ");
a2[0] = a1[0];
a2[1] = a1[3];
System.out.print(
CRT(s, a2, 2) + " ");
a2[0] = a1[2];
a2[1] = a1[1];
System.out.print(
CRT(s, a2, 2) + " ");
a2[0] = a1[2];
a2[1] = a1[3];
System.out.print(
CRT(s, a2, 2) + " ");
}
}
}
// Driver Code
public static void
main(String[] args) throws Exception
{
// Given Number N
BigInteger N = new BigInteger("188");
// Given product of Prime Number
BigInteger P = new BigInteger("437");
// Function Call
solve(N, P);
}
}
25 44 393 412
Complejidad de Tiempo: O(√P + logN)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA