Introducción
En la actualidad los números primos son muy usados, tanto en la criptografía como en las firmas digitales, para ello sería muy bueno tener un algoritmo o un conjunto de algoritmos, capaz de generar eficientemente, primos de longitudes grandes.
A pesar de que tengamos dichos algoritmos, se pueden presentar varios problemas y puede suceder que los números primos que estemos generando no nos sirvan, para ello debemos tener en cuenta varios puntos.
Debemos garantizar que los números que estamos generando son realmente primos o con una altísima probabilidad lo sean. Comprobar si un número es compuesto o primo, se puede tratar de varias maneras, una muy simple es factorizarlo, así con solo mostrar los factores primos, convenceríamos sin tener que mostrar una teoría compleja o argumentos auxiliares. Otra forma bastante parecida seria encontrarle un divisor a dicho número, con esto lo demostraríamos de manera sencilla a cualquier persona. Pero como persuadir a alguien si el numero es primo, para esto debemos acudir a teorías auxiliares, que serán simples o complejas según el nivel de fortaleza de nuestro algoritmo, con las cuales se demuestran condiciones que debe cumplir un número para ser primo o no, de esta manera las comprobaríamos y en caso de cumplirse o no, sabríamos que es primo o compuesto algunas veces con seguridad y otras con una alta probabilidad.
Otra característica de los números que vamos a generar, es que nadie pueda obtenerlos, aunque tenga conocimiento del funcionamiento de nuestros algoritmos. Esto se puede lograr con el empleo de funciones que generan números aleatorios.
Una vez garantizadas ambas cosas, podemos confiar en los números primos obtenidos.
El problema de reconocer los números primos en los naturales, ha sido uno de los temas más antiguos y al que la comunidad científica le ha puesto siempre un gran esfuerzo a lo largo de la historia.
La criba de Eratóstenes es el método más antiguo (200 A. C. ) para encontrar números primos, es capaz de reconocer los primeros primos hasta un número dado, actualmente tiene más significado histórico que práctico, por su alto costo computacional. Siguiendo la misma idea el italiano Leonardo de Pisa (Fibonacci) presentó un algoritmo muy simple para determinar si un número n dado es primo, consistente en comprobar que ningún otro número primo inferior a la divide a n. Este algoritmo tiene la característica de ser determinista (siempre obtiene una solución) pero vuelve a ser completamente ineficiente.
El primer resultado importante se dio a conocer en 1876, cuando Èdouard Lucas presentó un algoritmo que permite determinar, de una manera asombrosamente eficiente, la primalidad de los números de Mersenne, hoy en día el primo más grande que se conoce es = 1, con 12. 978. 189 dígitos, encontrado por GIMPS/ Edson Smith el 23 de agosto del 2008.
Luego en ausencia de algoritmos deterministas, para determinar si un número cualquiera (sin ninguna forma o propiedad en particular) es primo, aparecen los llamados Test Probabilísticos de Primalidad, el primero en suceder es el Test de Fermat, basado en el Pequeño Teorema de Fermat (PTF) el cual tiene una gran eficiencia y nos da un alto grado de confiabilidad, pero este test tiene un Talón de Aquiles son los llamados números de Carmichael, que se reconocen en este test como primos, siendo realmente compuestos. Corrigiendo este detalle aparece el Test de Primalidad de Solovay-Strassen (SS) en y modificado en 1982 por Atkin y Larson. Pero es en 1980 que aparece el Test de Miller-Rabin el cual es el más usado en la actualidad, por ser sencillo de implementar, posee el mismo costo computacional que los anteriores y muestra una probabilidad superior.
Basado en las teorías de curvas elípticas, tenemos el famoso algoritmo ciclotómico de Adleman-Pomerance-Rumely (APRCL) determinista, el cual no es polinomial en los bits del número, pero es tremendamente eficiente en la práctica para determinar la primalidad de un número.
A pesar del esfuerzo en encontrar test de primalidad eficientes y deterministas, parecía imposible encontrarse con uno que fuese de orden polinomial en los bits del numero, es así que en agosto del 2002 sorprendiendo a la comunidad científica Manindra Agrawal, Neeraj Kayal y Nitin Saxena, del Departamento de Computación del Instituto de Investigaciones de Kanpur, en la India presentan el AKS, considerándose así, como el primer test determinista de orden polinomial.
Soy el mejor
Blogs Relacionados
- Day Light Saving Time 2010 In India | SpotThisNow
- 90% de probabilidad de victoria de GSP en UFC-111, pero St. Pierre …
- Opciones de seguridad de archivos PDF
- Are there any Data Providers for Latitudes and Longitudes of all …
- Pregunta abierta: que probabilidad tengo de estar embarazada …
- Divulgaciones » ¿Es el 1 un número primo?
- ¿Qué pasa si en Febrero se obtienen las firmas digitales en la …
- The latitudes and longitudes
- LawaLoca Punto Org » Blog Archive » 90% de probabilidad de …
- Bigger Isn't Always Better…
