viernes, 26 de junio de 2015

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:


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:



banner
Previous Post
Next Post

Hola, me llamo Andrés.Soy egresado de la carrera de Ingeniería Informática en la Universidad Nacional de Trujillo (Perú).Me considero autodidacta de corazón ,amante del mundo de la programación, software libre y hacking ético

3 comentarios:

  1. hola, buenas tardes, es que a mi no me sale por ejemplo quisiera sacar las raices de
    255 mod (751) y me da como resultado 401 cuando deberia ser 69

    ResponderEliminar
  2. Por si algun dia alguien lo requiere todo se debe a esto:
    public int CalcularExp(int a,int k,int z)
    {
    int exp=1;
    int xp=a%z;
    while(k>0)
    {
    if((k%2)!=0)
    {
    exp=(exp*xp)%z;
    }
    xp=(xp*xp)%z;
    k=k/2;//aqui debes poner k=Math.trunc(k/2);
    }
    return exp;
    }

    No hay problema en java ya que al hacer divisiones con enteros solo devuelve partes enteras, pero en javaScript no pasa eso, tenemos que poer la parte k=Math.trunc(k/2); para que esta solo se quede con la parte entera ese es el error, que parece pequeño pero si no se considera da resultados incorrectos.
    /*by lalo3431*/

    ResponderEliminar