thumb|El 39.º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. 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 de forma concluyente la hipótesis de un teorema cuya conclusión es que n es compuesto.
Esto es, un test de primalidad solo 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 acortar en tiempo polinomial.Papadimitriou, Christos H.: Computational Complexity. Sección 10.2: "Primality", pp.222–227. Addison-Wesley, 1era edición, 1993. (ISBN 0-201-53082-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í:
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 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 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 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.
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 () aunque hay evidencias de que el conocimiento de la existencia de estos números tan particulares se podría remontar a Pitágoras ().
Sin embargo, el primer procedimiento matemático conocido concerniente estos números se remonta a Eratóstenes () y es la conocida criba que lleva su nombre, 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, solo 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 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:
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úmero de 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.
Tests verdaderos de primalidad
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 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.
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 solo 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 determinista 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 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).