Diferencia entre revisiones de «Número primo»
Contenido eliminado Contenido añadido
Revertidos los cambios de 190.110.129.27 a la última edición de Comu nacho usando monobook-suite |
|||
Línea 62:
Posteriormente se encontraron algoritmos de primalidad con sólo obtener una factorización parcial de p+1 o p-1. Ejemplos de de estos algoritmos son el [[Teorema de Proth|test de Proth]] (desarrollado alrededor de 1878) y el [[test de Pocklington]] (1914). En estos algoritmos se requiere que el producto de los factores primos conocidos de p-1 sea mayor que la raíz cuadrada de ''p''. Más recientemente, en 1975, Brillhart, Lehmer y Selfridge desarrollaron el [[test BLS de primalidad]] que sólo requiere que dicho producto sea mayor que la raíz cúbica de ''p''. El mejor método conocido de esta clase es el [[test de Konyagin y Pomerance]] del año 1997 que requiere que dicho producto sea mayor que ''p''<sup>3/10</sup>.<ref>{{cita libro| apellidos = Crandall| nombre = Richard| título = Prime numbers, a computational perspective| año = 2001| editorial = Nueva York: Springer-Verlag| id = ISBN 0-387-94777-9}}</ref><ref>{{Cita web|apellido=Bernstein|nombre=Daniel|título=Prime tests|url=http://cr.yp.to/primetests.html|fechaacceso=1 de julio de 2009}}</ref>
A partir de la década de 1970 varios investigadores descubrieron algoritmos para determinar si cualquier número es primo o no con complejidad subexponencial, lo que permite realizar tests en números de miles de dígitos, aunque son mucho más lentos que los métodos anteriores. Ejemplos de estos algoritmos son el [[test de Adleman-Pomerance-Rumely|test APRT-CL]] (desarrollado en 1979 por Adleman, Pomerance y Rumely, con mejoras introducidas por Cohen y Lenstra en 1984), donde se usan los factores de p<sup>m</sup>-1, donde el exponente m depende del tamaño del número cuya primalidad se desea verificar, el [[test 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 si el número es primo o no. El desarrollo más reciente es el [[test de primalidad AKS]] (2002) que si bien su complejidad es polinómica, para los números que puede manejar la tecnología actual es el más
Durante mucho tiempo, se pensaba que la aplicación de los números primos era muy limitada fuera de la [[matemática pura]]<ref>{{cita libro
| |||