Header Ads

ad728
  • Posts recientes

    Problema de Raices Cuadradas Módulo n [código]

    El problema de calcular las raíces cuadradas módulo n (square roots module n problem), llamado también SQROOT es un problema muy usado como fundamento en diversas funciones criptográficas. Este problema tiene dos casos a solucionar, el primero cuando n es primo, en el cual el cálculo a realizar es fácil, pero si n es compuesto, el cálculo es difícil debido a que se desconoce los factores primos de n. En este post presentaremos el código fuente en java de una implementación de la solución de este problema.

    En esta implementación sencilla calcularemos la raíz cuadrada módulo n de manera independiente para cuando n es primo y compuesto. Así en nuestro código fuente en Java, calcularemos la raíz cuadrada de a módulo p.

    Empezamos con el caso en en que p es primo, se tendrá el resultados r o - r que representa la raíz cuadrada calculada, si el resultado es mayor que p se entenderá que se obtuvo un ERROR.

    1. private static long inv = 0; //variable global

      public static long SRPrimo(long a, long p)
    2. {
    3. long r=0;
    4. if(esCongruente(p,3,4)==true)
    5. r = SRPrimo1(a,p);
    6. else
    7. if(esCongruente(p,5,8)==true)
    8. r = SRPrimo2(a,p)
      else //resuelve cualquier caso,
    9. r = SRPrimoGeneral(a,p);//pero para un n muy
      // grande no es eficiente
    10. return r;
    11. }
    La función esCongruente() la pueden encontrar aquí. Luego:

    1. public static long SRPrimoGeneral(long a, long p)
    2. {
    3. int jac=jacobi(a,p); //hallamos el simbolo de jacobi
    4. System.out.println("Simbolo de jacobi de "+
      a+"modulo "+p+" es = "+jac);
    5. if(jac==-2)
    6. {
    7. System.out.println("Error!!"+a+
      " no pertenece a Z_"+p);
    8. return (p+1); //Error
    9. }
    10. if(jac==-1) //devolvera un numero fuera de rango,
    11. //lo que significa ERROR
    12. {
    13. System.out.println("Error!!"+a+" no tiene"+
      "raices modulo "+p);
    14. return (p+1); //a no tiene raiz cuadrada
      // modulo p
    15. }
    16. if(moduloInverso(a,p)==false)//si existe
      //modulo inverso, este se almacena en la var global inv
    17. {
    18. System.out.println("Error!"+a+" no tiene "+
      "inverso modulo "+p);
    19. return (p+1); //a no tiene raiz
      //cuadrada modulo p
    20. }
    21. long b,s,t,c,d,r=0;
    22. boolean flag=false;
    23. do{ //usamos la divison repetida por 2
    24. s = hallarExponente((int)(p-1));
    25. t = (int)((p-1)/(Math.pow(2,s)));
    26. }while(t%2==0); // t tiene que ser impar
    27. //ahora seleccionaremos enteros b.
    28. for(b=1; b<=p-1 && flag==false; b++)
    29. {
    30. jac = jacobi(b,p);
    31. if(jac==-1) //b no es residuamente
      //cuadratico modulo p
    32. {
    33. flag = true;
      //el resultado de a^-1 mod p, se almaceno
      // en la variable global llamada inv
    34. c = exponenciacionModular(b,t,p);
    35. r = exponenciacionModular(a,((t+1)/2),p);
    36. for(int i=1; i<=s-1; i++)
    37. {
    38. d = exponenciacionModular((r*r*inv),
      ((long)Math.pow(2,s-i-1)),p);
    39. System.out.println(" d = "+d);
    40. if(esCongruente(d,-1,p)==true)
    41. r = (r*c)%p;
    42. c = exponenciacionModular(c,2,p);
    43. System.out.println(" r = "+r);
    44. }
    45. }
    46. }
    47. System.out.println(" s = "+s);
      System.out.println(" t = "+t);
    48. return r;
    49. }
    El símbolo de Jacobi que calcula la función jacobi() y hallarExponente() se encuentran aqui, mientras que la función moduloInverso() y exponenciacionModular() lo encuentran en este post.

    1. //CASO 1: cuando p es congruente con 3 modulo 4
    2. public static long SRPrimo1(long a, long p)
    3. {
    4. System.out.println("Estamos en el caso 1");
    5. long r=0;
    6. int jac=jacobi(a,p); //hallamos el simbolo de jacobi
    7. System.out.println("Simbolo de jacobi de "+a+
      "modulo "+p+" es = "+jac);
    8. if(jac==1)
    9. r = exponenciacionModular(a,((p+1)/4),p);
    10. else
    11. {
    12. System.out.println("Error! "+a+
      " no pertenece a Q_"+p);
    13. return (p+1); //Errrorrrrrr
    14. }
    15. return r;
    16. }
    17. //CASO 2: cuando p es congruente con 5 modulo 8
    18. public static long SRPrimo2(long a, long p)
    19. {
    20. System.out.println("Estamos en el caso 2");
    21. long r=0,d=0;
    22. int jac=jacobi(a,p); //hallamos el simbolo de jacobi
    23. System.out.println("Simbolo de jacobi de "+a+
      "modulo "+p+" es = "+jac);
    24. if(jac==1)
    25. {
    26. d = exponenciacionModular(a,((p-1)/4),p);
    27. if(d==1)
    28. r = exponenciacionModular(a,((p+3)/8),p);
    29. if(d==p-1)
    30. r = (2*a*((long)Math.pow(4*a,
      ((p-5)/8))))%p;
    31. }
    32. else
    33. {
    34. System.out.println("Error! "+a+
      " no pertenece a Q_"+p);
    35. return (p+1); //Error
    36. }
    37. return r;
    38. }
    Finalmente, para el caso en que p es compuesto.

    1. public static long[] SRCompuesto(long a, long n)
    2. {
    3. long[] resp = new long[4];
    4. boolean band = false;
    5. long p,q;//factores no triviales de n
    6. p = pollardRho(n);
    7. q = n/p;
    8. System.out.println(" "+n+" = "+p+"x"+q);
    9. long r=0,s=0,x=0,y=0;
    10. do{
    11. r = SRPrimoEspecial(a,p);
    12. s = SRPrimoEspecial(a,q);
    13. //si todo salio OK hasta ahora, entonces seguimos
    14. long[] euc = new long[3];
    15. euc = euclidesExtendido(p,q);
    16. long c = euc[1];
    17. long d = euc[2];
    18. //resto chino
    19. x = ((r*d*q)+(s*c*p))%n;
    20. y = ((r*d*q)-(s*c*p))%n;
    21. //probamos si la respuesta es valida o no
    22. if(esCongruente(x*x,a,n) &&
      esCongruente(y*y,a,n))
    23. band = true;
    24. }while(band==false);
    25. resp[0] = x;
    26. resp[1] = -x;
    27. resp[2] = y;
    28. resp[3] = -y;
    29. return resp;
      }
    30. public static long SRPrimoEspecial(long a, long p)
    31. {
    32. if(moduloInverso(a,p)==false)//si existe modulo inverso,
      //este se almacena en la var global inv
    33. {
    34. System.out.println("Error! "+a+
      " no tiene inverso modulo "+p);
    35. return (p+1); //a no tiene raiz cuadrada modulo p
    36. }
    37. long b,s,t,c,d,r=0;
    38. boolean flag=false;
    39. do{ //usamos la divison repetida por 2
    40. s = hallarExponente((int)(p-1));
    41. t = (int)((p-1)/(Math.pow(2,s)));
    42. }while(t%2==0); // t tiene que ser impar
    43. long jac;
    44. //ahora seleccionaremos enteros b.
    45. do{
    46. b =(long)Math.floor(Math.random()*(p-1));
    47. }while(b<1 || b>p-1);
    48. jac = jacobi(b,p);
    49. if(jac==-1) //b no es residuamente
      //cuadratico modulo p
    50. {
    51. //el resultado de a^-1 mod p, se almaceno
      //en la variable global llamada: inv
    52. c = exponenciacionModular(b,t,p);
    53. r = exponenciacionModular(a,((t+1)/2),p);
    54. for(int i=1; i<=s-1; i++)
    55. {
    56. d = exponenciacionModular((r*r*inv),
      ((long)Math.pow(2,s-i-1)),p);
    57. if(esCongruente(d,-1,p)==true)
    58. r = (r*c)%p;
    59. c = exponenciacionModular(c,2,p);
    60. }
    61. }
    62. return r;
    63. }

    Para esta condición hacemos uso del algoritmo de Pollard Rho para enfrentar el problema de la factorización entera, el código lo pueden encontrar aquí.

    Con las funciones presentadas arriba, podemos usar en nuestra función principal una llamada para calcular la raíz cuadrada módulo n según sea el caso:

    1. public static void main(String[] args){
    2. //Prueba raices cuadradas modulo p, p primo
    3. long a =12;//12345;
    4. long p =37;//1234533;
    5. long r = SRPrimo(a,p);
    6. if(r<p && esCongruente(r*r, a,p) )//verificamos
    7. System.out.println("La raiz cuadrada de "+
    8. a+" modulo "+p+" es = "+r+" y "+-r);
    9. //Prueba raices cuadradas modulo n, n compuesto
    10. long c=11;
    11. long n=1315;
    12. long[] resp = new long[4];
    13. resp = SRCompuesto(c,n);
    14. for(int i=0; i<4; i++){
    15. if(resp[i]<n)//verificacion
    16. System.out.println(" raiz"+(i+1)+
    17. " es = "+resp[i]+" ==>: "+
    18. resp[i]+"^2 mod "+n+" = "+c);
    19. else
    20. i = 4;//ya no imprime nada
    21. }
    22. else
    23. System.out.println("ERROR");
    24. }


    Quieres leer más post como éste???...suscribete aquí!!!

    No hay comentarios.

    Bienvenido a jcGeorge's Blog!!!

    Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

    Gracias por leer este blog!!!

    Related Posts Plugin for WordPress, Blogger...

    Post Top Ad

    Post Bottom Ad

    ad728