RAIZ CUADRADA MODULAR CUANDO N ES NUMERO PRIMO

El problema de la raíz cuadrada modulo «n» es muy usado en criptografía, donde para hallar la raíz se debe tener en cuenta que un número entero «n» es primo o tal vez compuesto. Si «n» es primo, entonces la raíz cuadrada módulo n es fácilmente obtenida, pero si «n» es un número compuesto entonces hallar tal raíz es difícil ya que sus factores primos son desconocidos.
En este post veremos la implementación  de la raíz cuadrada cuando n es primo.

Algoritmo:

Implementación:
La operación de Raíz cuadrada es una que combina varios conocimientos previos como son:

•  Euclides Extendido (Ver publicación).
• La inversa modular (Ver publicación).
• La exponenciación modular (Ver publicación).
• Multiplicación modular
• Símbolo de Jacobi (Ver publicación).

Por lo que recomendamos ver las publicaciones referentes a cada una ya que por motivos de comodidad solo mencionare cada función:

Función Multiplicación Modular:

public int CalcularMultiplicacion(int a,int b,int z)
    {
        int respuesta;
        respuesta=(a*b)%z;
        return respuesta;
    }

Función Exponencial:

public int funcion_exponencial(int a)
    {
        int c=0;
        while(a%2==0)
        {
            a=a/2;
            c++;
        }
        return c;
    }

Función Raíz Cuadrara:

public class Raiz {
    boolean bandera=true;
    int raiz[]= new int[2];

    public int[] getRaiz() {
        return raiz;
    }

    public int funcion_exponencial(int a)
    {
        int c=0;
        while(a%2==0)
        {
            a=a/2;
            c++;
        }
        return c;
    }
    public boolean CalcularRaiz(int p,int a)
    {
       int aux=0,auxc=0,b = 0,s=0,t,Ia=0,c=0,r=0,d=0,base=0,exponente=0,aux_exp;
        Jacobi obj = new Jacobi();
        if(obj.Opjacobi(a,p)==-1)
        {
            bandera=false;
            return bandera;
        }
        
        while(aux!=-1)
        {
            auxc++;
            aux=obj.Opjacobi(auxc, p);
            b=auxc;
        }
        
        s=funcion_exponencial(p-1);
        aux_exp=(int)Math.pow(2,s);
        t= ((p-1)/aux_exp);
        Inverso inv= new Inverso();
        Ia=(int) inv.CalcularInverso((long)a, (long)p);
        Exponenciacion exp = new Exponenciacion();
        c=exp.CalcularExp(b, t, p);
        r=exp.CalcularExp(a, ((t+1)/2), p);
        for(int i=1;i<=s-1;i++)
        {
            base=r*r*Ia;
            exponente=(int) Math.pow(2,s-i-1);
            d=exp.CalcularExp(base,exponente,p);
            if((d+1)%p==0)
            {
                Multiplicacion mul=new Multiplicacion();
                r=mul.CalcularMultiplicacion(r, c, p);
            }
        }
        System.out.println(r);
        c=exp.CalcularExp(c, 2, p);
        this.raiz[0]=r;
        this.raiz[1]=-r;
        return bandera;
    }
}

Fragmento de codigo de Interfaz Principal

        boolean rpta;
        int raices[]=new int[2];
        Raiz obj = new Raiz();
        rpta=obj.CalcularRaiz(Integer.parseInt(numero_p.getText()),Integer.parseInt(numero_a.getText()));
        if(rpta==false)
        {
            JOptionPane.showMessageDialog(null, "NO EXISTEN RAICES");
        }
        else
        {
            raices=obj.getRaiz();
            raiz_1.setText(String.valueOf(raices[0]));
            raiz_2.setText(String.valueOf(raices[1]));
        }

Bueno espero que les sea de utilidad esta es una de las operaciones mas importantes de la criptografía , en otra publicación realizare la implementación de la raíz cuadrada pero para números compuestos.

Actualización

Aquí les dejo la implementacion cuando N es un numero compuesto:

• Algoritmo de la Raíz Cuadrada Modular cuando N es Numero Compuesto en Java

• Tweet
• Share
• Share
• Share
• Share