Búscalo aquí:

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.:

Publicar un comentario

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...