Test de primalidade

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ómico^[1]

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
    
     $P\gets$ Número aleatorio do intervalo  $[n,2n]$ 
    mentres  $P\,\!$ non primo 
         $P\gets P+1$ 
        se  $(P=2n)\,\!$ entón  $P\gets n$ 
    retorna  $P\,\!$

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 $\mathbb {N}$ é 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 $\mathbb {N} _{n}^{*}$ 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 . $n/{\log \,n}$ 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 ${\sqrt {n}}$ .

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 $n$ . 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. $2^{n}-1$ $n$ $2^{n-1}(2^{n}-1)$ 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. $M_{p}=2^{p}-1$ 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). $M_{p}$

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 $q|2^{37}-1$ .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:

Este resultado é importante, xa que presenta a proba como unha secuencia sinxela de pasos lineal en n onde todas as operacións básicas (produtos, restas, módulos, comparacións) son computables en tempo polinómico.

O problema obvio que ten esta proba é a xeneralidade, xa que só se pode aplicar aos números de Mersenne.

O segundo algoritmo de proba de primalidade aplícase a números n xenéricos e supón que se coñece unha factorización parcial de n–1. Baséase no teorema de Pocklington.^[2]

O algoritmo é sinxelo. Limítase a realizar unha serie de cálculos con aritmética modular e comprobar o resultado. A contrapartida é que necesitase unha factorización parcial de n.

Existe un resultado menos xeral que o de Pocklington que é debido a outro matemático do século XIX (o teorema de Proth). Pero como se dixo é menos xeral e ten a mesma aplicación, polo que non entraremos en detalles.

A última proba neste apartado débese a Pepin (1877). O teorema de Pépin enúnciase como segue:

A constante 3 en realidade pódese substituír por calquera enteiro positivo para o que un operador chamado símbolo de Jacobi sexa igual a–1. Isto inclúe aos valores 3, 5 e 10.

Así como a proba LKL só se pode aplicar aos números de Mersenne, a proba de Pepin só se pode aplicar aos números de Fermat, polo que o seu uso (como no caso de LKL) queda bastante restrinxido.

Tests probabilísticos

Os tests probabilísticos están baseados na idea de relaxar a corrección da proba para conseguir un comportamento de resposta polinomial ou subpolinomial. Baséanse ben no uso PTF (que acabamos de comentar), ben no uso do que se coñecen como verificadores e falsadores de Euler.

O primeiro exemplo de test probabilístico que veremos é o test de Fermat. Devandito test está baseado no PTF. O algoritmo baseado neste test aplícase elixindo varios enteiros aleatorios entre 2 e n-2 e calculando . $a$ $r\equiv a^{n-1}{\pmod {n}}$ Si algún valor de é distinto de 1 o algoritmo devolve composto, noutro caso devolve primo. $r$ A fortaleza deste test radica en que tras un número normalmente pequeno de repeticións a probabilidade de que un número composto pase como primo é moi pequena.

Como vimos na sección anterior, o test de Fermat adoece dun coñecido problema: os números de Carmichael. Os números de Carmichael pasan a condición de Fermat para todos os posibles valores de ; isto implica que se o noso candidato a número primo fose un número de Carmichael, non importa cantas veces pasemos o test de Fermat, o resultado sempre sería negativo e en consecuencia o resultado do test sería un falso primo positivo. $a$ Con todo, os números de Carmichael son relativamente escasos (hai 105.212 deles menores de ) polo que a probabilidade de elixir algún deles é realmente baixa. $10^{15}$ O test de Fermat é de amplo uso no campo da criptografía.

Outro test moi coñecido e utilizado en criptografía é o test de Solovay-Strassen (SS). Este test está baseado no criterio de Euler.

Avances recentes

Desde os anos 70 estívose traballando na mellora dos algoritmos clásicos para obter mellores probas de primalidade.^[3] Para iso traballouse coa factorización de formas polinómicas de n. Entre estes algoritmos destacan o debido a Adleman, Pomerance e Rumely (APR) e a mellora que sobre este fixeron Cohen e Lenstra (APR-CL) que obteñen complexidades case polinomiais.

Tamén se está avanzando neste campo utilizando outras formas máis sinxelas de traballo con grupos matemáticos en lugar da aritmética modular dos grupos de Galois.

Neste sentido están a facerse avances no traballo con curvas elípticas módulo n. Unha curva elíptica é unha función que se define da seguinte forma:

E(a,b):\quad y^{2}=x^{3}+ax+b\quad /\quad 4a^{3}+27b^{2}\neq 0

En curvas deste tipo estiveron traballando desde 1986 Goldwasser, Kilian e Atkin. Este último definiu o método ECPP ou proba de primalidade por curva elíptica (Elliptic Curve Primality Proving), que ten diversas implementaciones e probouse que é de orde polinomial para case todas as entradas.

Moitas das probas e tests de primalidade que vimos até agora resólvense en tempo polinomial.

Durante anos os sistemas criptográficos estiveron utilizándoos para a xeración de claves seguras. Con todo teñen limitacións. Algúns non son probas de primalidade e en consecuencia non devolven un certificado de primalidade: existe unha probabilidade (aínda que pequena) de que un número sexa considerado primo cando en realidade é composto; son os que se coñecen como algoritmos probabilísticos de orde P (RP). Outros se que certifican a primalidade, pero non se garante que o test termine en tempo polinomial; son os que se coñecen como algoritmos deterministas de tempo polinomial probabilístico (ZPP). Algúns necesitan factorizacións parciais ou totais de n+1 e, como xa se viu, a factorización é un problema que non se pode resolver en tempo polinómico no caso xeral. Para outros a terminación en tempo polinomial baséase en certas conxecturas non probadas.

Por exemplo, o test de Miller é polinomial se a hipótese estendida de Riemann (ou conxectura ERH) é certa. Existe unha crenza xeneralizada na conxectura ERH, pero ao faltar unha demostración matemática non se pode concluír a súa terminación polinomial.

Test de primalidade AKS

O recente descubrimento dun algoritmo determinista de tempo polinomial que non se basea en ningunha conxectura non probada debe ser considerado un fito importante. Concretamente en agosto do ano 2002 tres académicos da Universidade de Kanpur (Agrawal, Kayal e Saxena) presentaron un algoritmo determinista de clase P para a determinación da primalidade dun número.^[4] A clave do algoritmo é unha versión simplificada do PTF, isto é a condición:

(x-a)^{p}\equiv (x^{p}-a){\pmod {x^{r}-1,\;p}}

Os autores arranxáronllas para formular o seguinte algoritmo, que se probou pode executarse nun tempo de complexidade máxima de . ${\mathcal {O}}((\log \,n)^{\frac {21}{2}}f(\log \;\log \,n))$

Os autores demostraron ademais que, se determinados números primos (chamados números primos de Sophie Germain) teñen a distribución conxecturada polo matemático austríaco Emil Artin, o expoñente 21/2 que aparece na expresión de complexidade pode reducirse a 15/2. O que implica que o tempo estimado de execución sería equivalente ao dalgunha proba de primalidade das vistas anteriormente (concretamente a proba ECPP). E no artigo publicado polos mesmos, tamén mencionaban unha versión do algoritmo AKS presentada por H.W. Lenstra e C. Pomerance que se executa en tempo de forma incondicional.^[5] ${\mathcal {O}}((\log \,n)^{6+\epsilon })$

En realidade este descubrimento non ten implicacións prácticas na computación moderna. O certo é que as partes constantes da complexidade do algoritmo son moito máis custosas que nos actuais algoritmos probabilísticos. É de esperar que no futuro próximo obtéñanse melloras nesas constantes, pero o certo é que os algoritmos actuais de xeración de números primos cobren bastante ben as necesidades actuais e, posiblemente, as futuras (e é pouco probable que a liña proposta mellore en tempo de execución aos algoritmos probabilísticos existentes). Con todo se que ten unha importancia fundamental desde o punto de vista teórico, xa que supón a primeira proba de primalidade destas características que foi matematicamente demostrada.

Notas

↑ Papadimitriou, Christos H.: Computational Complexity.
↑ Caldwell, Chris,Finding primes & proving primality
↑ Caldwell, Chris: The Prime Pages.
↑ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin: "PRIMES is in P".
↑ H. W. Lenstra jr. and Carl Pomerance: "Primality testing with Gaussian periods".

Referencias

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford: Introduction to Algorithms. Sección 31.8: "Primality testing", pp. 887–896. MIT Press & McGraw-Hill, 2a edición, 2001. (ISBN 0-262-03293-7.)
Crandall, Richard & Pomerance, Carl: Prime Numbers: A Computational Perspective Capítulo 3: "Recognizing Primes and Composites", pp. 109–158. Capítulo 4: "Primality Proving", pp. 159–190. Sección 7.6: "Elliptic curve primality proving (ECPP)", pp. 334–340. Springer, 1a edición, 2001. (ISBN 0-387-94777-9.)
Knuth, Donald. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Páxinas 391–396 de sección 4.5.4. Addison-Wesley, 3a edición, 1997. (ISBN 0-201-89684-2.)
Williams, H.C.: Édouard Lucas and Primality Testing. John Wiley & Sons, 1998. (ISBN 0-471-14852-0.)

Véxase tamén

Outros artigos

Ligazóns externas

Programa

Solovay-Strassen Proba de primalidade por Solovay-Strassen en Maple

En inglés

Agrawal, Kayal & Saxena: Primes is in P Instituto de Tecnoloxía Kanpur, India.
Bernstein, D.J.: Distinguishing prime numbers from composite numbers
Caldwell, Chris (en inglés).<meta /> The Prime Pages.<meta /> Universidade de Tennessee. http://primes.utm.edu .

[1] Papadimitriou, Christos H.: Computational Complexity.

[2] Caldwell, Chris,Finding primes & proving primality

[3] Caldwell, Chris: The Prime Pages.

[4] Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin: "PRIMES is in P".

[5] H. W. Lenstra jr. and Carl Pomerance: "Primality testing with Gaussian periods".

[1]

[2]

[3]

[4]

[5]