Buscar raíz cuadrada en Módulo p | (Cuando p es producto de dos números primos en la forma 4*i + 3)

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);
    }
}
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *