Test de primalidad
La cuestión de la determinación de si un número n dado es primo es conocida como el problema de la primalidad y es el problema que trataremos en este artículo.
Un test (o chequeo) de primalidad es un algoritmo que, dado un número de entrada n, no consigue verificar la hipótesis de un teorema cuya conclusión es que n es compuesto.
Esto es, un test de primalidad sólo conjetura que “ante la falta de certificación sobre la hipótesis de que n es compuesto podemos tener cierta confianza en que se trata de un número primo”. Esta definición supone un grado menor de confianza que lo que se denomina prueba de primalidad (o test verdadero de primalidad) que ofrece una seguridad matemática al respecto.
Introducción
Los problemas que implican a las matemáticas discretas están entre los más difíciles de las matemáticas. Concretamente el de la factorización es un problema para el que todavía no se ha encontrado una solución que se pueda acotar en tiempo polinomial [PAP93].
Por otra parte, algunas aplicaciones de las matemáticas que utilizan el problema de la factorización precisan de una serie de números primos muy grandes escogidos de forma aleatoria. El algoritmo para obtener un número primo aleatorio muy grande sería algo así:
ObtenerNumeroPrimoAleatorio () DEVUELVE retval:= ObtenerNúmeroAleatorioEnIntervalo [LÍMITESUPERIOR , LÍMITESUPERIOR ] MIENTRAS NO EsPrimo(retval) retval:= retval + 1 SI retval:= LÍMITESUPERIOR ENTONCES retval:= LÍMITESUPERIOR FIN MIENTRAS FIN ObtenerNumeroPrimoAleatorio
El tiempo de finalización de este algoritmo no es determinado, pero existe una alta probabilidad de que finalice en tiempo polinomial siempre y cuando haya suficientes números primos y estos estén distribuidos de forma más o menos uniforme. Afortunadamente para las aplicaciones que precisan números primos aleatorios, esto es así. Veamos por qué.
Lo primero que podemos establecer es que el cardinal del conjunto de primos en N es infinito (esto es que hay infinitos números primos). El teorema de Dirichlet (1837) dice que si mcd(a,n) = 1 entonces hay infinitos primos congruentes con (a mod n). En otras palabras (y utilizando un corolario de Dirichlet) que los números primos están uniformemente distribuidos en las clases congruentes con la función Phi de Euler en para cualquier valor de n.
Claro que, si los números primos están uniformemente distribuidos, pero hay un número pequeño de ellos, la búsqueda podría ser imposible en la práctica. Para resolver este segundo problema podemos acudir al teorema de Hadamard (1896) que establece que la cardinalidad del conjunto de números primos en el intervalo [2..n] es asintótico a . Este número tiende a cero muy suavemente, lo que implica que aún para valores grandes de n existe una probabilidad suficientemente alta de dar con un número primo de forma aleatoria.
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. Lo que nos devuelve al problema de la primalidad.
En cualquier caso una modificación muy frecuente para hacer el algoritmo determinista es partir de una semilla aleatoria y luego hacer una búsqueda secuencial de la cota inferior del conjunto de primos mayores que la semilla de partida:
De Euclides a Lucas
Antes de entrar a tratar las técnicas modernas que se aplican al problema de la primalidad no está de más hacer un breve repaso a la historia del problema y a las soluciones aportadas a lo largo de los siglos.
Los problemas de la factorización de un número dado y la determinación de números primos son muy antiguos. Los registros históricos sobre el estudio de números primos se remontan a Euclides (siglo III adC) aunque hay evidencias de que el conocimiento de la existencia de estos números tan particulares se podría remontar a Pitágoras (siglo VI adC).
Sin embargo, el primer procedimiento matemático conocido concerniente estos números se remonta a Eratóstenes (siglo II adC) y es la conocida criba de Eratóstenes, que todavía se estudia en las escuelas de educación primaria. El método es sencillo: para obtener los números primos menores que un dado, primero colocamos los números de 1 a en una lista y empezamos tachando todas las posiciones pares. Luego, sobre la lista que queda tachamos todos los que son múltiplo de tres (el siguiente número de la lista después del 2). Luego sobre los que quedan todos los que son múltiplos de cinco (el siguiente número de la lista después del 3).
Hoy día, este algoritmo tiene un valor más histórico que práctico. Funciona bien, pero es muy ineficiente.
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 menores que .
Otro problema de la criba es que no responde al problema de la simple determinación de primalidad de un número dado, sino que ofrece una lista (potencialmente infinita) de números primos.
El problema, más concreto, de determinar si un número dado es primo puede derivarse del anterior: simplemente se simula la criba para y se comprueba si permanece en ella. La cuestión es que el coste de seguir este procedimiento es muy grande.
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 divide a . Este algoritmo tiene la característica de ser determinista (siempre obtiene una solución) aunque tremendamente ineficiente. En realidad, Fibonacci es más conocido por la sucesión que lleva su nombre y que también tiene su papel en el problema que nos ocupa. Luego veremos algo más sobre la famosa sucesión de Fibonacci.
El primero en utilizar relaciones observadas entre los números para determinar la primalidad fue el boloñés Pietro Antonio Cataldi con su trabajo sobre los números perfectos.
Un número perfecto es aquel que es igual a la suma de sus divisores propios. Por ejemplo 6 es perfecto, ya que la suma de sus divisores (1+2+3) es igual al mismo. Los siete primeros números perfectos son 6, 28, 496, 8128, 33550336, 8589869056 y 137438691328.
Cataldi determinó que si es primo entonces ha de ser primo y ha de ser perfecto. Este teorema nos introduce una familia de números especialmente importante para la historia de la primalidad: los llamados números de Mersenne en honor del filósofo Marin Mersenne (1588-1665), que son números de la forma donde p es un número primo. Mersenne comprobó que de los 257 primeros números de la familia que lleva su nombre, sólo 11 son primos (son los para p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 y 257).
En realidad Mersenne cometió algunos errores ya que no es primo para p = 67 ni 257 y sí lo es para p = 61, 89 y 107; no obstante su trabajo sobre estos números ha quedado reflejado en el hecho de que llevan su nombre.
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). Fermat es posiblemente el teórico numérico más renombrado de la historia y es muy conocido por un teorema que ha estado sin demostración durante más de trescientos años. Con referencia a la primalidad, Fermat tuvo correspondencia con Mersenne y de hecho estableció un resultado sobre los números primos que es esencial para las técnicas modernas de determinación de la primalidad. El teorema en cuestión (conocido como Pequeño teorema de Fermat ó PTF) establece lo siguiente:
- Teorema: Sea , entonces...
- .
- Teorema: Sea , entonces...
Como corolario a este importante teorema se establece que si es primo, entonces cualquier número primo que divida a tiene que ser de la forma para algún . También se puede demostrar que si es el menor número tal que , entonces siempre que .
Fermat buscaba números que le ayudaran a comprobar la primalidad de los números de Mersenne. En su búsqueda vio que el teorema antes expuesto era útil para detectar posibles primos tales que . Fermat también sugirió que los números de la forma (denominados números de Fermat y representados por ) debían ser primos y lo comprobó para todos los n menores que 4. No pudo demostrarlo para y hoy se sabe que es compuesto, como lo son todos los restantes hasta (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. Euler se sintió atraído por los resultados de Fermat y encontró un divisor de (contradiciendo pues la conjetura de Fermat sobre la primalidad de ). Sin embargo, su aportación más importante al problema fue el enunciado de un teorema relacionado que establece que todo divisor primo de debe ser de la forma para algún .
Hubo otros matemáticos también muy eminentes que trabajaron en el campo de la factorización de números, por ejemplo Legendre y Gauss, y que también hicieron algunas contribuciones al problema de la primalidad; pero el último de los matemáticos clásicos del que hablaremos que obtuvo notables resultados sobre la cuestión fue el francés François Éduard Anatole Lucas. Lucas trabajó sobre los números de Fibonacci y de Mersenne, obtuvo resultados sobre la divisibilidad de los primeros y determinó una prueba de primalidad para los números de Mersenne (que aplicó a la comprobación de primalidad de ) que veremos a continuación.
Test verdaderos de primalidad
En los apartados anteriores hemos hablado de dos problemas relacionados (factorización y primalidad) que de alguna manera son complementarios. Sin embargo, las dos cuestiones son de naturaleza muy distinta. 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. Como el matemático parisino del siglo XIX Fortuné Landry señaló, a menos que la otra parte conozca los métodos de comprobación de la primalidad y realice por si misma los cálculos, la sencilla respuesta “es primo” es sólo cuestión de fe. Un test (o chequeo) de primalidad es un algoritmo que, dado un número de entrada n, no consigue verificar la hipótesis de un teorema cuya conclusión es que n es compuesto.
Esta es la visión del matemático; desde el punto de vista del ingeniero las cosas no son blancas o negras. Por ello, convenimos en diferenciar los tests (o chequeos) de las pruebas. Antes de proseguir, ha llegado el momento de definir formalmente ambos conceptos.
- Definición: Un test (o chequeo) de primalidad es un algoritmo que, dado un número de entrada n, no consigue verificar la hipótesis de un teorema cuya conclusión es que n es compuesto.
Esto es, un test de primalidad sólo conjetura que “ante la falta de certificación sobre la hipótesis de que n es compuesto podemos tener cierta confianza en que se trata de un número primo”. Esta definición supone un grado menor de confianza que lo que se denomina prueba de primalidad (o test verdadero de primalidad) que ofrece una seguridad matemática al respecto.
- Definición: Un algoritmo de prueba de primalidad (o test verdadero de primalidad) es un algoritmo determinístico que, dado un número de entrada n, verifica la hipótesis de un teorema cuya conclusión es que n es primo. Una prueba de primalidad es la verificación computacional de dicho teorema.
Así pues podemos hablar de dos grados de certidumbre: las pruebas de primalidad (existe certidumbre matemática) y los tests de primalidad (existe certidumbre práctica).
Nuestro interés es fundamentalmente la aplicación práctica de las técnicas. Sin embargo, es interesante ver algo sobre las pruebas. En esta primera sección nos ocuparemos de éstas y veremos algunos de los test clásicos de primalidad, dejando para un apartado posterior una discusión sobre el grupo de algoritmos complementario que, aunque no prueban la primalidad con certidumbre matemática resultan mucho más interesantes al ser computablemente más estables y predecibles.
Para empezar, veremos el ejemplo clásico de test verdadero de primalidad: el test de Lucas-Kraitchik-Lehmer. La prueba LKL se aplica a los números de Mersenne (la entrada es el índice n del número de Mersenne del que se quiere comprobar la primalidad). La definición del algoritmo es la siguiente:
LKM ( INPUT n > 1 COMO Entero ) DEVUELVE {primo, compuesto} s1:= 4 PARA TODO j DESDE 1 HASTA n – 1 sj:= sj-1² - 2(mod Mn) FIN PARA TODO SI sn-1 ENTONCES DEVUELVE primo EN OTRO CASO DEVUELVE compuesto FIN LKM
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.
El problema obvio que tiene esta prueba es la generalidad, ya que sólo se puede aplicar a los números de Mersenne.
El segundo algoritmo de prueba de primalidad que veremos se aplica a números n genéricos y supone que se conoce una factorización parcial de n – 1. Se basa en el teorema de Pocklington. Dicho teorema establece lo siguiente:
- Teorema: tal que y , donde tiene una factorización en números primos conocida:
- Si
- (i) , y
- (ii) .
- Entonces , ; de lo que se deduce que si entonces n es primo.
- Si
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 primos.
Veamos un ejemplo de prueba por Pocklington para el número n=57283. Supongamos conocida la factorización parcial n–1=6∙9547 y también conocido el hecho de que 9547 es un número primo. Puesto que , pero , podemos concluir que n es primo.
El algoritmo es sencillo. Se limita a realizar una serie de cálculos con aritmética modular y comprobar el resultado. La contrapartida es que se necesita una factorización parcial de n.
Existe un resultado menos general que el de Pocklington que es debido a otro matemático del siglo XIX (el teorema de Proth). Pero como se ha dicho es menos general y tiene la misma aplicación, por lo que no entraremos en detalles.
La última prueba que veremos en este apartado se debe a Pepin (1877). El teorema de Pepin se enuncia como sigue:
- Teorema: , el número de Fermat enésimo, definido por es primo si y sólo si .
La constante 3 del test de Pepin en realidad se puede sustituir por cualquier entero positivo para el que un operador llamado símbolo de Jacobi sea igual a –1. Esto incluye a los valores 3, 5 y 10.
Así como la prueba LKL sólo se puede aplicar a los números de Mersenne, la prueba de Pepin sólo se puede aplicar a los números de Fermat, por lo que su uso (como en el caso de LKL) queda bastante restringido.
Lo que subyace a estas pruebas es esencialmente el resultado que se desprende del PTF. Si el teorema inverso fuese cierto (esto es si la comprobación de la condición an-1=1 módulo n, para cualquier a primo relativo de n implicase la primalidad de n) la prueba de primalidad sería un asunto muy sencillo. Sin embargo, existe una familia de números compuestos que cumplen la condición y que, por tanto, invalidan la posibilidad de realizar una prueba por el inverso del PTF; estos números se denominan Números de Carmichael por el matemático que los descubrió. Un ejemplo de número de Carmichael es n=561. Hablaremos de ellos en la próxima sección.
Test probabilísticos
Los test probabilísticos están basados en la idea de relajar la corrección de la prueba para conseguir un comportamiento de respuesta polinomial o subpolinomial. Se basan bien en el uso PTF (que acabamos de comentar), bien en el uso de lo que se conocen como verificadores y falsadores de Euler.
El primer ejemplo de test probabilístico que veremos es el test de Fermat. Dicho test está basado en el PTF. El algoritmo basado en este test se aplica eligiendo varios enteros aleatorios a entre 2 y n-2 y calculando . Si algún valor de es distinto de 1 el algoritmo devuelve compuesto, en otro caso devuelve primo. La fortaleza de este test radica en que tras un número normalmente pequeño de repeticiones la probabilidad de que un número compuesto pase como primo es muy pequeña.
Como vimos en la sección anterior, el test de Fermat adolece de un conocido problema: los números de Carmichael. Los números de Carmichael pasan la condición de Fermat para todos los posibles valores de a, esto implica que si nuestro candidato a número primo fuese un número de Carmichael, no importa cuantas 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. Sin embargo, los números de Carmichael son relativamente escasos (hay 105.212 de ellos menores de ) por lo que la probabilidad de elegir alguno de ellos es realmente baja. El test de Fermat es de amplio uso en el campo de la criptografía.
Otro test muy conocido y utilizado en criptografía es el test de Solovay-Strassen (SS). Este test está basado en el criterio de Euler que establece que si n es un número primo impar, entonces para todos los enteros que satisfacen que el mcd(a,n)=1, donde representa el símbolo de Jacobi definido por
donde cada es un primo distinto, y es el símbolo de Legendre definido por
Los valores de a que cumplen el criterio de Euler de denominan verificadores de Euler para la primalidad de n y los que no lo cumplen se denominan falsadores de Euler para la primalidad de n.
El test SS se podría codificar de la siguiente manera:
SS ( INPUT n > 1 COMO Entero ) DEVUELVE {primo, compuesto} PARA TODO j DESDE 1 HASTA t a:= Aleatorio entre 2 y n-2 SI DEVUELVE compuesto /* El símbolo de Jácobi */ SI DEVUELVE compuesto FIN PARA TODO DEVUELVE primo FIN SS
El test SS tiene una probabilidad de acierto de ½ por cada paso de j. Esto implica que la probabilidad de que la entrada sea compuesto habiendo sido declarado como primo es menor que ½t. Este test fue descubierto en 1978 y fue modificado en 1982 por Atkin y Larson, pero hoy por hoy está en desuso. El motivo es que el test que vamos a estudiar a continuación es más eficiente que el test SS y, al menos, tiene el mismo nivel de corrección.
El test más implantado en la actualidad es el Miller-Rabin (también conocido como test fuerte del pseudoprimo). El test de Miller-Rabin (MR) está basado en el siguiente hecho: Si tenemos un número primo n y donde r es impar, se cumple que , entonces o bien o bien .
El test MR se podría codificar de la siguiente manera:
MR ( INPUT n > 1 COMO Entero ) DEVUELVE {primo, compuesto} Definir s y r tal que r es impar y PARA TODO i DESDE 1 HASTA t a:= número aleatorio entre 2 y n-2 SI ( ) Y ( ) ENTONCES j:= 1 MIENTRAS Y SI y=1 DEVUELVE compuesto j:= j+1 FIN MIENTRAS SI DEVUELVE compuesto FIN SI FIN PARA TODO DEVUELVE primo FIN MR
El error cometido en cada paso de iteración es de ¼, (el diseño hace que existan más falsadores de Euler que en SS) por lo que la probabilidad de que la entrada sea un número compuesto habiendo sido declarado como primo es menor que ¼t. Por otra parte, al utilizar exponenciación binaria las operaciones necesarias se realizan rápidamente.
De los tres test probabilísticos aquí presentados el mejor desde el punto de vista técnico y práctico es el de Miller-Rabin. El test SS es computacionalmente peor y más difícil de implementar ya que hay que calcular el símbolo de Jacobi. Por otra parte ambos tienen la ventaja frente al de Fermat de que podemos aumentar la confianza de la primalidad con un valor de t arbitrariamente alto (Fermat tiene el límite definido por los números de Carmichael).
Métodos exóticos
Desde los años 70 se ha estado trabajando en la mejora de los algoritmos clásicos para obtener mejores pruebas de primalidad [PRI02]. Para ello se ha trabajado con la factorización de formas polinómicas de n. Entre estos algoritmos destacan el debido a Adleman, Pomerance y Rumely (APR) y la mejora que sobre éste hicieron Cohen y Lenstra (APR-CL) que obtienen complejidades casi polinomiales.
También se está avanzando en este campo utilizando otras formas más sencillas de trabajo con grupos matemáticos en lugar de la aritmética modular de los grupos de Galois.
En este sentido se están haciendo avances en el trabajo con curvas elípticas módulo n. Una curva elíptica es una función que se define de la siguiente forma:
En este sentido han estado trabajando desde 1986 Goldwasser, Kilian y Atkin. Este último definió el método ECPP que tiene diversas implementaciones y que ha probado es de orden polinomial para casi todas las entradas.
Últimos avances en la comprobación de la primalidad
Muchas de las pruebas y tests de primalidad que hemos visto hasta ahora se resuelven en tiempo polinomial.
Durante años los sistemas criptográficos han estado utilizándolos para la generación de claves seguras. Sin embargo tienen limitaciones. Algunos no son pruebas de primalidad y en consecuencia no devuelven un certificado de primalidad: existe una probabilidad (aunque pequeña) de que un número sea considerado primo cuando en realidad es compuesto; son los que se conocen como algoritmos probabilísticos de orden P (RP). Otros sí que certifican la primalidad, pero no se garantiza que el test termine en tiempo polinomial; son los que se conocen como algoritmos deterministas de tiempo polinomial probabilístico (ZPP). Algunos necesitan factorizaciones parciales o totales de n+1 y, como ya se se ha visto, la factorización es un problema que no se puede resolver en tiempo polinómico en el caso general. Para otros la terminación en tiempo polinomial se basa en ciertas conjeturas no probadas.
Por ejemplo, el test de Miller es polinomial si la hipótesis extendida de Riemann (o conjetura ERH) es cierta. Existe una creencia generalizada en la conjetura ERH, pero al faltar una demostración matemática no se puede concluir su terminación polinomial.
Por ello, el reciente descubrimiento de un algoritmo determinista de tiempo polinomial que no se basa en ninguna conjetura no probada debe ser considerado un hito importante. Concretamente en agosto del año 2002 tres académicos de la Universidad de Kanpur (Agrawal, Kayal y Saxena) presentaron [AKS02] un algoritmo determinista de clase P para la determinación de la primalidad de un número. 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 .
AKS ( INPUT n > 1 COMO ) DEVUELVE {primo, compuesto} SI (n tiene la forma con b > 1) ENTONCES DEVUELVE compuesto r := 2 MIENTRAS ( r < n ) SI mcd ( n, r ) ≠ 1 ENTONCES DEVUELVE compuesto SI ( r es primo mayor que 2 ) ENTONCES q := mayor factor de r - 1 SI ENTONCES SALIR MIENTRAS FIN SI r := r + 1 FIN MIENTRAS PARA TODO a DESDE 1 HASTA SI ( ) ENTONCES DEVUELVE compuesto FIN PARA TODO DEVUELVE primo FIN AKS
Los autores demostraron además que si determinados números primos (llamados Primos de Sophie Germain) tienen la distribución conjeturada por un matemático llamado Ardí, el exponente 12 que aparece en la expresión de complejidad puede reducirse a 6. Lo que implica que el tiempo estimado de ejecución sería equivalente al de alguna prueba de primalidad de las vistas anteriormente (concretamente la prueba ECPP).
En realidad este descubrimiento no tiene implicaciones prácticas en la computación moderna. Lo cierto es que las partes constantes de la complejidad del algoritmo son mucho más costosas que en los actuales algoritmos probabilísticos. Es de esperar que en el futuro cercano se obtengan mejoras en esas constantes, pero lo cierto es que los algoritmos actuales de generación de números primos cubren bastante bien las necesidades actuales y, posiblemente, las futuras (y es poco probable que la línea propuesta mejore en tiempo de ejecución a los algoritmos probabilísticos existentes). Sin embargo si que tiene una importancia fundamental desde el punto de vista teórico, ya que supone la primera prueba de primalidad de estas características que ha sido matemáticamente demostrada.
Referencias y bibliografía
[AKS02] Agrawal, Kayal & Saxena. PRIMES is in P. Indian Institute of Technology Kanpur. Primes is in P (ing)
[PRI02] Caldwell, Chris, The Prime Pages. Universidad de Tennessee. The Prime Pages (ing)
[PAP93] Papadimitriou, Christos H., Computational Complexity. Addison-Wesley, 1993. ISBN 0-201-53082-1
[WIL98] Williams, H.C., Édouard Lucas and Primality Testing. John Wiley & Sons, 1998. ISBN 0-471-14852-0