Búscalo aquí:

Residuos Cuadráticos [código]

En Teoría de Números uno de los conceptos más utilizados es el de residuo cuadrático módulo m a cualquier entero r primo con m para el que tenga solución la congruencia: x^2 = r (mod m), o lo que es lo mismo cuando r es un cuadrado perfecto módulo m, y que por lo tanto tiene una raíz cuadrada en la aritmética de módulo m. A los enteros que no son congruentes con cuadrados perfectos módulo m se les denomina no-residuos cuadráticos.



Esta definición es muy importante y será utilizada en muchos algoritmos de cifrado (encriptación) de información.

El código fuente en Java de la función que calcula los residuos cuadráticos es presentado a continuación:

  1. /*
  2. @author : Jorge Valverde
  3. */
  4. private static int[] Q;
  5. private static int[] NQ;
  6. private static void residuosCuadraticos(long n)
  7. {
  8. int tam = (int)(n-1)/2;
  9. Q = new int[tam];
  10. NQ = new int[tam];
  11. long g = getGenerador(n);
  12. int i=0,k=0,a=1,r=0;
  13. while(i<(n-1))
  14. {
  15. //donde 0<=n
  16. {
  17. Q[k] = a;
  18. k++;
  19. }
  20. }
  21. i=i+2;
  22. }
  23. for(a=1; a<n; a++)
  24. {
  25. if(buscar(a,Q)==false)
  26. {
  27. NQ[r] = a;
  28. r++;
  29. }
  30. }
  31. }

-->Los vectores de enteros Q y NQ declarados como variables globales servirán para almacenar respectivamente los elementos que son residuos cuadráticos y los que no lo son, respectivamente.

El código de la función para determinar la congruencia modular es el siguiente:

  1. /*
  2. @author: Jorge Valverde
  3. */
  4. private static boolean esCongruente(long a,long b,long n)
  5. {
  6. if((a-b)%n==0)
  7. return true;
  8. return false;
  9. }

-->El código fuente de la función buscar es el siguiente:

  1. /*
  2. @author: Jorge Valverde
  3. */
  4. private static boolean buscar(int a, int[] arreglo)
  5. {
  6. boolean band=false;
  7. for(int i=0; i<arreglo.length && band==false; i++)
  8. if(a==arreglo[i])
  9. band = true;
  10. return band;
  11. }

-->La función getGenerador() encuentra una semilla o generador usando la factorización de enteros basada en el algoritmo de Pollard Rho. El código fuente en Java de la función getGenerador() basado en el algoritmo de Pollard Rho lo pueden encontra AQUI.

Espero les sea de utilidad, saludos.




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