Test de primalidad
Afortunadamente para las aplicaciones que precisan números primos aleatorios, esto es así.
De lo visto hasta aquí podemos concluir que el algoritmo anterior puede obtener una respuesta en tiempo polinomial si existe un algoritmo polinomial para comprobar que un número n arbitrariamente grande es primo.
Sin embargo, el primer procedimiento matemático conocido concerniente estos números se remonta a Eratóstenes (siglo II a. C.) y es la conocida criba que lleva su nombre, que todavía se estudia en las escuelas de educación primaria.
La mejora más obvia atañe a la forma en la que el algoritmo termina (curiosamente Eratóstenes no tuvo en cuenta este hecho y fue el matemático árabe ibn al-Banna quien la propuso siglos después): es suficiente con iterar hasta los divisores primos de
dado es primo puede derivarse del anterior, simplemente se simula la criba para
Como muchas otras aportaciones matemáticas, el problema de la primalidad llegó a la Europa moderna a través de los árabes, pero no fue hasta muchos siglos después que aparecieron los primeros registros escritos sobre la primalidad y su solución.
Estos corresponden al matemático italiano Leonardo de Pisa (Fibonacci) quien 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
Este algoritmo tiene la característica de ser determinista (siempre obtiene una solución) aunque tremendamente ineficiente.
Por ejemplo 6 es perfecto, ya que la suma de sus divisores (1+2+3) es igual al mismo.
Contemporáneo de Mersenne y mucho más importante para la historia y el estado del arte actual del problema que estamos tratando fue el importante matemático Pierre de Fermat (1607-1665).
En su búsqueda vio que el teorema antes expuesto era útil para detectar posibles primos
) debían ser primos y lo comprobó para todos los n menores que 4.
(y posiblemente todos los demás, aunque este último extremo es aún una conjetura).
Otro eminente matemático que estuvo interesado en el problema de la primalidad fue el suizo Leonhard Euler.
Para convencer a alguien de que un número ha sido factorizado es suficiente con mostrar los factores y el resultado queda claro.
Sin embargo convencer a esa misma persona de que un número dado es primo puede ser mucho más difícil.
Este resultado es importante, ya que presenta la prueba como una secuencia sencilla de pasos lineal en n donde todas las operaciones básicas (productos, restas, módulos, comparaciones) son computables en tiempo polinómico.
[2] Dicho teorema establece lo siguiente: Así, si se conoce la factorización de un divisor de F se pueden concluir por el contraste con las condiciones (i) y (ii) que un número dado es primo.
Se limita a realizar una serie de cálculos con aritmética modular y comprobar el resultado.
Pero como se ha dicho es menos general y tiene la misma aplicación, por lo que no entraremos en detalles.
El algoritmo basado en este test se aplica eligiendo varios enteros aleatorios
; esto implica que si nuestro candidato a número primo fuese un número de Carmichael, no importa cuántas veces pasemos el test de Fermat, el resultado siempre sería negativo y en consecuencia el resultado del test sería un falso primo positivo.
El test de Miller-Rabin (MR) está basado en el siguiente hecho: Si tenemos un número primo n y
Por otra parte, al utilizar exponenciación binaria las operaciones necesarias se realizan rápidamente.
Este último definió el método ECPP o prueba de primalidad por curva elíptica (Elliptic Curve Primality Proving), que tiene diversas implementaciones y se ha probado que es de orden polinomial para casi todas las entradas.
Durante años los sistemas criptográficos han estado utilizándolos para la generación de claves seguras.
Existe una creencia generalizada en la conjetura ERH, pero al faltar una demostración matemática no se puede concluir su terminación polinomial.
La clave del algoritmo es una versión simplificada del PTF, esto es la condición: Los autores se las arreglaron para formular el siguiente algoritmo, que se ha probado puede ejecutarse en un tiempo de complejidad máxima de
Los autores demostraron además que, si determinados números primos (llamados números primos de Sophie Germain) tienen la distribución conjeturada por el matemático austriaco Emil Artin, el exponente 21/2 que aparece en la expresión de complejidad puede reducirse a 15/2.
Y en el artículo publicado por los mismos, también mencionaban una versión del algoritmo AKS presentada por H.W.
