Tension Superficial

Historia de los números primos
Durante el siglo XIX se desarrollaron algoritmos para saber si un número es primo o no factorizando completamenteel número siguiente (p+1) o el anterior (p-1). Dentrodel primer caso se encuentra el test de Lucas-Lehmer,desarrollado a partir de 1856. Dentro del segundo caso se encuentra el test de Pépin para los números de Fermat(1877). El caso general de test deprimalidad cuando el número inmediatamente anterior se encuentra completamentefactorizado se denomina test de Lucas.Posteriormente se encontraron algoritmos de primalidad con sólo obtener unafactorización parcial de p+1 o p-1.Ejemplos de de estos algoritmos son el test de Proth (desarrollado alrededor de 1878) y el test de Pocklington (1914).En estos algoritmos se requiere que el producto de losfactores primos conocidos de p-1 sea mayor que la raízcuadrada de p. Más recientemente, en 1975, Brillhart, Lehmer y Selfridge desarrollaron el test BLS de primalidadque sólo requiere que dichoproducto sea mayor que la raíz cúbica de p. El mejor método conocido de esta clase es eltest de Konyagin y Pomerance del año 1997 que requiere que dicho producto sea mayor que p
A partir de la década de1970 varios investigadores descubrieron algoritmos para determinar si cualquier número esprimo o no con complejidad subexponencial, lo que permite realizar tests en números de miles de dígitos, aunquesonmucho más lentos que los métodos anteriores. Ejemplos de estos algoritmos son el test APRT-CL (desarrolladoen 1979 por Adleman, Pomerance y Rumely, con mejoras introducidas por Cohen y Lenstra en1984), donde se usanlos factores de p m-1, donde el exponente m depende del tamaño del número cuya primalidad se desea verificar, eltest de primalidad por curvas elípticas (desarrollado en 1986 por S.Goldwasser, J. Kilian y mejorado por A. O. L.Atkin), que entrega un certificado consistente en una serie de números que permite después confirmar rápidamente siel número es primo o no. El desarrollo...