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. Un test de primalidad (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.

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 acortar en tiempo polinomial.^[1]​

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í:

/*Basado en el postulado de Bertrand*/

Entrada: Un número natural n.

Salida : P (el número primo aleatorio buscado).

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 el conjunto de los números naturales ${displaystyle mathbb {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 módulo n. En otras palabras (y utilizando un corolario de Dirichlet), los números primos están uniformemente distribuidos en las clases congruentes con la función φ de Euler en ${displaystyle mathbb {N} _{n}^{*}}$ 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 ${displaystyle n/{log ,n}}$. Este número tiende a infinito 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.

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 a. C.) 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 a. C.).

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 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 ${displaystyle n}$ dado, primero colocamos los números de 1 a ${displaystyle n}$ 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 ${displaystyle n}$ menores que ${displaystyle {sqrt {n}}}$.

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 ${displaystyle n}$ dado es primo puede derivarse del anterior, simplemente se simula la criba para ${displaystyle n-1}$ y se comprueba si ${displaystyle n}$ 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 ${displaystyle {sqrt {n}}}$ divide a ${displaystyle n}$. 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 ${displaystyle 2^{n}-1}$ es primo entonces ${displaystyle n}$ ha de ser primo y ${displaystyle 2^{n-1}(2^{n}-1)}$ 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 ${displaystyle M_{p}=2^{p}-1}$ donde p es un número primo. Mersenne comprobó que de los 257 primeros números de la familia que lleva su nombre, solo 11 son primos (son los ${displaystyle M_{p}}$ para p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 y 257).

En realidad Mersenne cometió algunos errores ya que ${displaystyle M_{p}}$ 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 esencialmente estuvo 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 o PTF) establece lo siguiente:

Teorema: Sea ${displaystyle b,,qin mathbb {N} ;/;q{mbox{ es primo }}wedge ;q mid b}$, entonces...

Como corolario a este importante teorema se establece que si ${displaystyle p>2}$ es primo, entonces cualquier número primo ${displaystyle q}$ que divida a ${displaystyle 2^{p}-1}$ tiene que ser de la forma ${displaystyle q=2mp+1}$ para algún ${displaystyle min mathbb {N} }$. También se puede demostrar que si ${displaystyle min mathbb {N} }$ es el menor número tal que ${displaystyle n|(b^{m}-1)}$, entonces ${displaystyle q|(b^{t}-1)}$ siempre que ${displaystyle q|t}$.

Fermat buscaba números ${displaystyle n>1}$ 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 ${displaystyle q}$ tales que ${displaystyle q|2^{37}-1}$. Fermat también sugirió que los números de la forma ${displaystyle 2^{2^{n}}+1}$ (denominados números de Fermat y representados por ${displaystyle {mathfrak {F}}_{n}}$) debían ser primos y lo comprobó para todos los n menores que 4. No pudo demostrarlo para ${displaystyle {mathfrak {F}}_{5}}$ y hoy se sabe que ${displaystyle {mathfrak {F}}_{5}}$ es compuesto, como lo son todos los restantes hasta ${displaystyle n=24}$ (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 ${displaystyle {mathfrak {F}}_{n}}$ (contradiciendo pues la conjetura de Fermat sobre la primalidad de ${displaystyle {mathfrak {F}}_{5}}$). Sin embargo, su aportación más importante al problema fue el enunciado de un teorema relacionado que establece que todo divisor primo de ${displaystyle {mathfrak {F}}_{n}}$ debe ser de la forma ${displaystyle 2^{n+1}k+1}$ para algún ${displaystyle kin mathbb {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 ${displaystyle M_{127}}$) que veremos a continuación.

En los apartados anteriores se ha 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 sí 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.

Ésta 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.

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.

Así pues se puede hablar de dos grados de certidumbre: las pruebas de primalidad (existe certidumbre matemática) y los tests de primalidad (existe certidumbre práctica).

El interés, fundamentalmente, es la aplicación práctica de las técnicas. Sin embargo, es interesante ver algo sobre las pruebas. En esta primera sección se ocupa de éstas y de 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, el ejemplo clásico de test verdadero de primalidad: el Test de Lucas-Lehmer. La prueba LL se aplica a los números de Mersenne (la entrada es el índice p del número de Mersenne del que se quiere comprobar la primalidad). La definición del algoritmo es la siguiente:

Entrada: Un número primo p.

Salida: COMPUESTO si M_p es compuesto y PRIMO si M_p es un primo.

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 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.^[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.

Un ejemplo de prueba por Pocklington para el número n=57283. Se supone conocida la factorización parcial n–1=6∙9547 y también conocido el hecho de que F=9547 es un número primo, por tanto q es único e igual a F. Puesto que ${displaystyle 2^{n-1}equiv 1{pmod {n}}}$, y ${displaystyle operatorname {mcd} (a^{frac {n-1}{q}}-1,n)=1}$, 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-1.

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 en este apartado se debe a Pepin (1877). El teorema de Pepin se enuncia como sigue:

La constante 3 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 a^n-1≡1 (mod 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.

Los tests 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 ${displaystyle a}$ entre 2 y n-2 y calculando ${displaystyle requiv a^{n-1}{pmod {n}}}$. Si algún valor de ${displaystyle r}$ 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 ${displaystyle a}$; 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. Sin embargo, los números de Carmichael son relativamente escasos (hay 105.212 de ellos menores de ${displaystyle 10^{15}}$) 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 ${displaystyle a^{frac {(n-1)}{2}}equiv left({frac {a}{n}} ight){pmod {n}}}$ para todos los enteros que satisfacen que el mcd(a,n)=1, donde ${displaystyle left({frac {a}{n}} ight)}$ representa el símbolo de Jacobi definido por

donde cada ${displaystyle p_{j}}$ es un primo distinto, ${displaystyle e_{j}in mathbb {N} }$ y ${displaystyle left({frac {a}{p_{j}}} ight)}$ es el símbolo de Legendre definido por

Los valores de ${displaystyle a}$ que cumplen el criterio de Euler se 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:

Entrada: Un número natural n>1, el número k de veces que se ejecuta el test y nos determina la fiabilidad del test.

Salida: COMPUESTO si n es compuesto y POSIBLE PRIMO si n es un posible primo.

El test SS tiene una probabilidad de acierto de ½ por cada paso de j. Esto implica que la probabilidad de que la entrada sea un número 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 ${displaystyle n-1=2^{s}r}$ donde r es impar, se cumple que ${displaystyle forall ;ain mathbb {N} ;/;{mbox{mcd}}(a,n)=1}$, entonces o bien ${displaystyle a^{r}equiv 1{pmod {n}}}$ o bien ${displaystyle exists jin [0,s-1]quad /quad a^{2^{j}r}equiv -1{pmod {n}}}$.

El test MR se podría codificar de la siguiente manera:

Entrada: Un número natural n>1, el número k de veces que se ejecuta el test y nos determina la fiabilidad del test.

Salida: COMPUESTO si n es compuesto y POSIBLE PRIMO si n es un posible primo.

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 tests 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).

Desde los años 70 se ha estado trabajando en la mejora de los algoritmos clásicos para obtener mejores pruebas de primalidad.^[3]​ 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 curvas de este tipo han estado trabajando desde 1986 Goldwasser, Kilian y Atkin. 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.

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 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.

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^[4]​ 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 ${displaystyle {mathcal {O}}((log ,n)^{frac {21}{2}}f(log ;log ,n))}$.

Entrada: Un número natural n > 1.

Salida: COMPUESTO si n es compuesto y PRIMO si n es primo.

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. 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). Y en el artículo publicado por los mismos, también mencionaban una versión del algoritmo AKS presentada por H.W. Lenstra y C. Pomerance^[5]​ que se ejecuta en tiempo ${displaystyle {mathcal {O}}((log ,n)^{6+epsilon })}$ de forma incondicional.

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 sí 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.

---