miniatura|O 39.º número primo de Mersenne era o maior coñecido até a data de creación deste artigo. A cuestión da determinación de se un número n dado é primo é coñecida como o problema da primalidade. Un test de primalidade (ou recoñecemento da primalidade) é un algoritmo que, dado un número de entrada n, non consegue verificar a hipótese dun teorema cuxa conclusión é que n é composto.
Isto é, un test de primalidade só conxectura que “ante a falta de certificación sobre a hipótese de que n é composto podemos ter certa confianza en que se trata dun número primo”. Esta definición supón un grao menor de confianza que o que se denomina proba de primalidade (ou test verdadeiro de primalidade), que ofrece unha seguridade matemática respecto diso.
Introdución Os problemas que implican ás matemáticas discretas están entre os máis difíciles das matemáticas. Concretamente o da factorización é un problema para o que aínda non se atopou unha solución que se poida acoutar en tempo polinómicoPapadimitriou, Christos H.: Computational Complexity.
Por outra banda, algunhas aplicacións das matemáticas que utilizan o problema da factorización precisan dunha serie de números primos moi grandes escollidos de forma aleatoria. O algoritmo para obter un número primo aleatorio moi grande sería algo así:
algoritmo baseado no postulado de Bertrand é entrada: Un número natural n saída: P, o primo aleatorio buscado
Número aleatorio do intervalo mentres non primo
se entón retorna
O tempo de finalización deste algoritmo non é determinado, pero existe unha alta probabilidade de que finalice en tempo polinómico a condición de que haxa suficientes números primos e estes estean distribuídos de forma máis ou menos uniforme. Afortunadamente para as aplicacións que precisan números primos aleatorios, isto é así. Vexamos por que.
O primeiro que podemos establecer é que o cardinal do conxunto de primos no conxunto dos números naturais é infinito (isto é, que hai infinitos números primos). O teorema de Dirichlet (1837) di que se mcd(a, n) = 1 entón hai infinitos primos congruentes con a módulo n. Noutras palabras (e utilizando un corolario de Dirichlet), os números primos están uniformemente distribuídos nas clases congruentes coa función φ de Euler en para calquera valor de n.
Claro que, se os números primos están uniformemente distribuídos, pero hai un número pequeno deles, a procura podería ser imposible na práctica. Para resolver este segundo problema podemos acudir ao teorema de Hadamard (1896) que establece que a cardinalidade do conxunto de números primos no intervalo [2..n] é asintótico a . Este número tende a infinito moi suavemente, o que implica que aínda para valores grandes de n existe unha probabilidade suficientemente alta de dar cun número primo de forma aleatoria.
Do visto até aquí podemos concluír que o algoritmo anterior pode obter unha resposta en tempo polinomico se existe un algoritmo polinomial para comprobar que un número n arbitrariamente grande é primo. O que nos devolve ao problema da primalidade.
En calquera caso, unha modificación moi frecuente para facer o algoritmo determinista é partir dunha semente aleatoria e logo facer unha procura secuencial da cota inferior do conxunto de primos maiores que a semente de partida.
De Euclides a Lucas Antes de entrar a tratar as técnicas modernas que se aplican ao problema da primalidade non está de máis facer un breve repaso á historia do problema e ás solucións achegadas ao longo dos séculos.
Os problemas da factorización dun número dado e a determinación de números primos son moi antigos. Os rexistros históricos sobre o estudo de números primos remóntanse a Euclides (século III a. C.) aínda que hai evidencias de que o coñecemento da existencia destes números tan particulares poderíase remontar a Pitágoras (século VI a. C.).
Con todo, o primeiro procedemento matemático coñecido concernente estes números remóntase a Eratóstenes (século II a. C.) e é a coñecida criba de Eratóstenes, que aínda se estuda nos centros de educación primaria. O método é sinxelo: para obter os números primos menores que un dado, primeiro colocamos os números de 1 a n nunha lista e empezamos tachando todas as posicións pares. Logo, sobre a lista que queda tachamos todos os que son múltiplo de tres (o seguinte número da lista despois do 2). Logo sobre os que quedan todos os que son múltiplos de cinco (o seguinte número da lista despois do 3).
Hoxe en día, este algoritmo ten un valor máis histórico que práctico. Funciona ben, pero é moi ineficiente.
A mellora máis obvia atén á forma na que o algoritmo termina (curiosamente Eratóstenes non tivo en conta este feito e foi o matemático árabe ibn ao-Banna quen a propuxo séculos despois): é suficiente con iterar até os divisores primos de n menores que .
Outro problema da criba é que non responde o problema da simple determinación de primalidade dun número dado, senón que ofrece unha lista (potencialmente infinita) de números primos.
O problema, máis concreto, de determinar se un número n dado é primo pode derivarse do anterior, simplemente simúlase a criba para n-1 e compróbase se permanece nela. A cuestión é que o custo de seguir este procedemento é moi grande.
Como moitas outras achegas matemáticas, o problema da primalidade chegou á Europa moderna a través dos árabes, pero non foi até moitos séculos despois que apareceron os primeiros rexistros escritos sobre a primalidade e a súa solución. Estes corresponden ao matemático italiano Leonardo de Pisa (Fibonacci) quen presentou un algoritmo moi simple para determinar se un número n dado é primo consistente en comprobar que ningún outro número primo inferior á raíz cadrada de n divide a . Este algoritmo ten a característica de ser determinista (sempre obtén unha solución) aínda que tremendamente ineficiente. En realidade, Fibonacci é máis coñecido pola sucesión que leva o seu nome e que tamén ten o seu papel no problema que nos ocupa. Logo veremos algo máis sobre a famosa sucesión de Fibonacci.
O primeiro en utilizar relacións observadas entre os números para determinar a primalidade foi o boloñés Pietro Antonio Cataldi co seu traballo sobre os números perfectos.
Un número perfecto é aquel que é igual á suma dos seus divisores propios. Por exemplo 6 é perfecto, xa que a suma dos seus divisores (1+2+3) é igual ao mesmo. O sete primeiros números perfectos son 6, 28, 496, 8128, 33550336, 8589869056 e 137438691328.
Cataldi determinou que se é primo entón ha de ser primo e ha de ser perfecto. Este teorema introdúcenos unha familia de números especialmente importante para a historia da primalidade: os chamados números de Mersenne en honra do filósofo Marin Mersenne (1588-1665), que son números da forma onde p é un número primo. Mersenne comprobou que dos 257 primeiros números da familia que leva o seu nome, só 11 son primos (son os para p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 e 257).
En realidade Mersenne cometeu algúns erros xa que M_p non é primo para p = 67 nin 257 e se o é para p = 61, 89 e 107; no entanto o seu traballo sobre estes números quedou reflectido no feito de que levan o seu nome.
Contemporáneo de Mersenne e moito máis importante para a historia e a estado da arte actual do problema que estamos a tratar foi o importante matemático Pierre de Fermat (1607-1665). Fermat é posiblemente o teórico numérico máis renomeado da historia e é moi coñecido por un teorema que esencialmente estivo sen demostración durante máis de trescentos anos. Con referencia á primalidade, Fermat tivo correspondencia con Mersenne e, de feito, estableceu un resultado sobre os números primos que é esencial para as técnicas modernas de determinación da primalidade.
Fermat buscaba números n>1 que lle axudasen a comprobar a primalidade dos números de Mersenne.Na súa procura viu que o teorema antes exposto era útil para detectar posibles primos q tales que .Fermat tamén suxeriu que os números denominados números de Fermat debían ser primos e comprobouno para todos os n menores que 4. Non puido demostralo para 5 e hoxe sábese que iso é composto, como o son todos os restantes até n=24 (e posiblemente todos os demais, aínda que este último extremo é aínda unha conxectura).
Outro eminente matemático que estivo interesado no problema da primalidade foi o suízo Leonhard Euler. Euler sentiu atraído polos resultados de Fermat.
Houbo outros matemáticos tamén moi eminentes que traballaron no campo da factorización de números, por exemplo Legendre e Gauss, e que tamén fixeron algunhas contribucións ao problema da primalidade; pero o último dos matemáticos clásicos do que falaremos que obtivo notables resultados sobre a cuestión foi o francés François Éduard Anatole Lucas. Lucas traballou sobre os números de Fibonacci e de Mersenne, obtivo resultados sobre a divisibilidad dos primeiros e determinou unha proba de primalidade para os números de Mersenne (que aplicou á comprobación de primalidade de M127) que veremos a continuación.
Tests verdadeiros de primalidade Nos apartados anteriores falouse de dous problemas relacionados (factorización e primalidade) que dalgunha maneira son complementarios. Con todo, as dúas cuestións son de natureza moi distinta. Para convencer a alguén de que un número foi factorizado é suficiente con mostrar os factores e o resultado queda claro. Con todo convencer a esa mesma persoa de que un número dado é primo pode ser moito máis difícil. Como o matemático parisiense do século XIX Fortuné Landry sinalou, a menos que a outra parte coñeza os métodos de comprobación da primalidade e realice por se mesma os cálculos, a sinxela resposta “é primo” é só cuestión de fe. Un test (ou recoñecemento) de primalidade é un algoritmo que, dado un número de entrada n, non consegue verificar a hipótese dun teorema cuxa conclusión é que n é composto.
Esta é a visión do matemático; desde o punto de vista do enxeñeiro as cousas non son brancas ou negras. Por iso, convimos en diferenciar os tests (ou recoñecementos) das probas. Antes de proseguir, chegou o momento de definir formalmente ambos os conceptos. Definición: Un test (ou recoñecemento) de primalidade é un algoritmo que, dado un número de entrada n, non consegue verificar a hipótese dun teorema cuxa conclusión é que "n" é composto.Isto é, un test de primalidade só conxectura que “ante a falta de certificación sobre a hipótese de que n é composto podemos ter certa confianza en que se trata dun número primo”. Esta definición supón un grao menor de confianza que o que se denomina proba de primalidade (ou test verdadeiro de primalidade) que ofrece unha seguridade matemática respecto diso. Definición: Un algoritmo de proba de primalidade (ou test verdadeiro de primalidade) é un algoritmo determinista que, dado un número de entrada n, verifica a hipótese dun teorema cuxa conclusión é que n é primo. Unha proba de primalidade é a verificación computacional de devandito teorema.Así pois pódese falar de dous graos de certidumbre: as probas de primalidade (existe certidumbre matemática) e os tests de primalidade (existe certidumbre práctica).
O interese, fundamentalmente, é a aplicación práctica das técnicas. Con todo, é interesante ver algo sobre as probas. Nesta primeira sección ocúpase destas e dalgúns do test clásicos de primalidade, deixando para un apartado posterior unha discusión sobre o grupo de algoritmos complementario que, aínda que non proban a primalidade con certidumbre matemática resultan moito máis interesantes ao ser computablemente máis estables e predicibles.
Para empezar, o exemplo clásico de test verdadeiro de primalidade: o Test de Lucas-Lehmer. A proba LL aplícase aos números de Mersenne (a entrada é o índice p do número de Mersenne do que se quere comprobar a primalidade). A definición do algoritmo é a seguinte: