Test de primalitat

La qüestió de determinar si un nombre donat n és primer es coneix com el problema de la primalitat. Un test de primalitat, test de primeritat^[1] (o revisió de primalitat) és un algorisme que, donat un nombre d'entrada n, no aconsegueix verificar la hipòtesi que n és compost.

Per tant, un test de primalitat només afirma que "davant de la falta de verificació de la hipòtesi: n és compost, es pot tenir certa confiança de què es tracta d'un nombre primer". Aquesta definició implica un grau menor de confiança que amb una prova de primalitat (o test verdader de primalitat), que n'ofereix la seguretat matemàtica (confiança=1).

El problema de la Factorització és un problema per al qual no s'ha trobat una solució de Temps polinòmic.^[2]

D'altra banda, algunes aplicacions com ara en criptografia necessiten una sèrie de nombres primers molt grans escollits de forma aleatòria. L'algorisme per obtenir un nombre primer aleatori molt gran pot ser així:

El temps d'acabament d'aquest algorisme és, de mitjana:

${\displaystyle \left[1p+2p\left(1-p\right)+3p\left(1-p\right)^{2}+...\right]t}$

On ${\displaystyle t}$ és el temps de trobar un nombre aleatori més el temps de verificar si aquest nombre és primer (o verificar que no és compost) i ${\displaystyle p}$ és la probabilitat que un nombre a l'atzar entre n i 2n sigui primer.

La probabilitat que un nombre triat a l'atzar entre n i 2n sigui primer es pot estimar a partir del teorema dels nombres primers en:

${\displaystyle p={\frac {2}{\log 2n}}-{\frac {1}{\log n}}}$

Aquesta probabilitat és força gran, fins i tot per a nombres molt grans, per exemple la probabilitat que un nombre entre ${\displaystyle 1\cdot 10^{10}}$ i ${\displaystyle 2\cdot 10^{10}}$ sigui primer, resulta ser aproximadament d'un 1%.

Per tant la clau està en el temps necessari per a determinar si un nombre és primer o no. L'interès dels tests de primalitat radica en la possibilitat d'utilitzar algorismes que tenen un temps inferior al de les proves de primalitat i al mateix temps una probabilitat d'error (acceptar com a primer un nombre que no ho és) molt baixa.

Els problemes de la factorització d'un nombre donat i la determinació de nombres primers són molt antics. Els registres històrics sobre l'estudi de nombres primers es remunten a Euclides (segle iii aC) encara que hi ha evidències que el coneixement de l'existència d'aquests nombres es remunta a Pitàgores (segle vi aC). Tanmateix, el primer procediment matemàtic conegut per a determinar-los es remunta a Eratòstenes (segle II aC), el garbell d'Eratòstenes: Per a obtenir els nombres primers més petits que un ${\displaystyle n}$ donat, primer es col·loquen els nombres de l'1 a l'${\displaystyle n}$ en una llista i es ratllen totes les posicions parelles tret de la primera (el 2). Després, es ratllen tots els que són múltiples de tres tret del tres (a partir del primer nombre no ratllat, el 3, comptant de tres en tres). Després, els que són múltiples de cinc tret del cinc (el següent nombre de la llista sense ratllar després del 3, comptant de cinc en cinc). I així successivament. Un cop s'ha arribat a un nombre que sigui més gran que ${\displaystyle {\sqrt {n}}}$ s'atura l'algorisme. Els nombres que han quedat sense ratllar, són tots els nombres primers més petits que ${\displaystyle n}$.

La versió original de l'algorisme del garbell d'Erastòstenes no s'acabava en ${\displaystyle {\sqrt {n}}}$. Va ser el matemàtic àrab Ibn al-Bannà qui va proposar aquesta millora.

L'algorisme del garbell d'Estòstenes troba tots els nombres primers més petits que un nombre donat. Però de vegades el que es necessita saber és només si un nombre donat és primer o no. Això es pot determinar amb el garbell, però el temps de càlcul és molt llarg (i el resultat diu més del que es necessita).

Els primers registres escrits de l'estudi dels nombres primers a l'Europa medieval, corresponen al matemàtic italià Leonardo de Pisa (Fibonacci). Fibonacci va presentar un algorisme per a determinar si un nombre donat és primer o no sense necessitat d'haver de determinar tots els nombres primers més petits que el nombre en qüestió. L'algorisme de Fiboncci consisteix a comprovar que cap altre nombre primer més petit que ${\displaystyle {\sqrt {n}}}$ divideix a ${\displaystyle n}$. El bolonyès Pietro Antonio Cataldi fou el primer a utilitzar les relacions observades entre els nombres per a determinar la primalidad en el seu treball sobre els nombres perfectes.

Un nombre perfecte és el que és igual a la suma dels seus divisors propis. Per exemple 6 és perfecte, ja que la suma dels seus divisors (1 + 2 +3) és igual a 6. Els set primers nombres perfectes són: 6, 28, 496, 8128, 33550336, 8589869056 i 137438691328.

Cataldi va determinar que si ${\displaystyle 2^{n}-1}$ és primer llavors ${\displaystyle n}$ ha de ser primer i ${\displaystyle 2^{n-1}(2^{n}-1)}$ ha de ser perfecte. Aquest teorema introdueix una família de nombres especialment important per a la història de la primalidad: els anomenats nombres de Mersenne en honor del filòsof Marin Mersenne (1588-1665), que són nombres de la forma ${\displaystyle M_{p}=2^{p}-1}$ on p és un nombre primer. Mersenne va comprovar que dels 257 primers nombres de la família que porta el seu nom, només 11 són primers (són els ${\displaystyle M_{p}}$ per a p =2, 3, 5, 7, 13, 17, 19, 31, 67, 127 i 257). De fet Mersenne va cometre alguns errors perquè ${\displaystyle M_{p}}$ no és primer per a p=67 ni 257 i sí que ho és per a p=61, 89 i 107.

Contemporani de Mersenne va ser Pierre de Fermat (1607-1665). Fermat va establir el teorema conegut com a Petit teorema de Fermat o PTF), estableix el següent:

Un corolari d'aquest teorema diu que si ${\displaystyle p>2}$ és primer, llavors quealsevol nombre primer ${\displaystyle q}$ que divideixi a ${\displaystyle 2^{p}-1}$ ha de ser de la forma ${\displaystyle q=2mp+1}$ per algun ${\displaystyle m\in \mathbb {N} }$. També es pot demostrar que si ${\displaystyle m\in \mathbb {N} }$ és el nombre més petit tal que ${\displaystyle n|(b^{m}-1)}$, llavors ${\displaystyle q|(b^{t}-1)}$ sempre que ${\displaystyle q|t}$.

Fermat s'adonà que el teorema anterior era útil para a detectar possibles nombres primers ${\displaystyle q}$ tales que ${\displaystyle q|2^{37}-1}$. Fermat també va suggerir que els nombres de la forma ${\displaystyle 2^{2^{n}}+1}$ (anomenats nombres de Fermat i representats per ${\displaystyle {\mathfrak {F}}_{n}}$) havien de ser primers i ho va comprovar per a tots els n més petits que 4. No ho va poder demostrar per a ${\displaystyle {\mathfrak {F}}_{5}}$ i avui se sap que ${\displaystyle {\mathfrak {F}}_{5}}$ és compost, com ho són tots fins a ${\displaystyle n=24}$ (i potser tots els altres, tot i que això encara és una conjectura).

Leonhard Euler va trobar un divisor de ${\displaystyle {\mathfrak {F}}_{n}}$ (contradient la conjectura de Fermat sobre la primalitat de ${\displaystyle {\mathfrak {F}}_{5}}$). Va enunciar el teorema que diu que tot divisor primer de ${\displaystyle {\mathfrak {F}}_{n}}$ ha de ser de la forma ${\displaystyle 2^{n+1}k+1}$ per a algun ${\displaystyle k\in \mathbb {N} }$.

François Éduard Anatole Lucas va treballar sobre els nombres de Fibonacci i de Mersenne, va obtenir resultats sobre la divisibilitat dels de Fibonacci i va crear una prova de primalitat per als nombres de Mersenne (que va fer servir per a comprovar la primalitat de ${\displaystyle M_{127}}$).

El problema de la factorització (trobar factors, primers o no, que multiplicats donen el nombre) i el de primalitat (saber si un nombre és primer) estan relacionats però tenen una naturalesa molt diferent. Per a saber que un nombre es pot descompondre en factors, n'hi ha prou en conèixer una descomposició, a partir d'aquí és fàcil comprovar que la factorització és correcta, només cal multiplicar els factors, no cal conèixer els mètodes per a trobar els factors. Però saber que un nombre és primer (que no es pot descompondre en factors) és molt més complicat. Com digué el matemàtic del segle xix Fortuné Landry tret que es coneguin els mètodes de comprovació i es realitzin el càlculs, l'expressió "és primer" només és qüestió de fe. Una test (o revisió) de primalitat és un algorisme que, a partir d'un nombre n, en no aconseguir verificar que és compost, fa que augmenti la credibilitat de l'afirmació "n és un nombre primer".

Aquesta és la visió matemàtica. En les aplicacions en enginyeria, per exemple en criptografia, el risc de considerar que un nombre és primer quan en realitat no ho és, consisteix en el fet que el grau de seguretat baixa en la mesura en què sigui més o menys fàcil descompondre el nombre. Hi ha dos enfocaments, per una banda si la probabilitat que el nombre sigui compost és molt petita i les claus es canvien molt sovint, l'efectivitat d'un criptoanàlisi que pretengui explotar aquesta feblesa pot ser menstenible, per altra banda, per explotar la feblesa cal tenir un algorisme que pugui descompondre el nombre en un temps de càlcul acceptable, per tant si el nombre no es pot descompondre amb els algorismes coneguts que tenen un temps de càlcul acceptable, encara que no sigui primer ofereix un nivell de seguretat acceptable. Per tot això cal definir formalment els conceptes de tests (o revisions) i de proves.

Definició: Un test (o revisió) de primalitat és un algorisme que, donat un nombre d'entrada n, no aconsegueix verificar la hipòtesi que diu "n és compost".

És a dir, abans de passar el test de primalitat, la probabilitat que un nombre escollit a l'atzar en un determinat conjunt sigui primer és el quocient entre la quantitat de nombres primers que hi ha al conjunt i la quantitat total de nombres que té el conjunt. Després de passar el test de primalitat, la probabilitat que el nombre sigui primer és el quocient entre la quantitat de nombres primers i la quantitat de nombres que passen el test (siguin o no primers). Si la quantitat de nombres que no sent primers passen el test és petita comparada amb la quantitat de nombres primers, aquesta probabilitat pot ser propera a 1.

Definició: Un algorisme de prova de primalitat (o test verdader de primalitat) és un algorisme determinístic que, donat un nombre d'entrada n, verifica que és cert el teorema: "n és primer". Una prova de primalitat és la verificació computacional d'aquest teorema.

Així doncs una diferència entre els tests i les proves és el grau de certesa: les proves de primalitat ofereixen la certesa total (probabilitat que el nombre sigui primer = 1) els test ofereixen una certesa parcial (probabilitat que el nombres sigui primer <1).

Tot seguit s'estudien les proves de primalitat.

L'exemple clàssic de test verdader de primalitat és la Prova de Lucas-Lehmer per a nombres de Mersenne. La prova LL s'aplica als nombres de Mersenne (l'entrada és l'índex p del nombre de Mersenne del qual es vol comprovar la primalitat). La definició de l'algorisme és la següent:

Algorisme Prova de Lucas-Lehmer per a nombres de Mersenne. (Ordre de complexitat ${\displaystyle {\mathcal {O}}(p^{3})}$)

Entrada: Un índex p. Sortida: COMPOST si Mp és compost y PRIMER si Mp és un nombre primer. Assignar ${\displaystyle s_{1}\gets 4}$ Assignar ${\displaystyle M_{p}\gets 2^{p}-1}$ Fer per a ${\displaystyle j\,\!}$ des de ${\displaystyle 2\,\!}$ fins a ${\displaystyle n-1\,\!}$ ${\displaystyle s_{j}\gets (s_{j-1}^{2}-2)\;{\bmod {\;}}M_{p}\,\!}$ Si ${\displaystyle s_{j-1}=0\,\!}$ llavors: Retorna PRIMER Si no, llavors Retorna COMPOST

Aquest resultat és important, ja que presenta la prova com una seqüència senzilla de passos, lineal en n, on totes les operacions bàsiques (productes, restes, mòduls, comparacions) són computables en temps polinòmic. El problema obvi que té aquesta prova és la manca de generalitat, ja que només es pot aplicar als nombres de Mersenne.

Aquest algorisme de prova de primalitat s'aplica a nombres n genèrics i suposa que es coneix una factorització parcial de n -1. Es basa en el teorema de Pocklington.^[3] Dit teorema estableix el següent:

Teorema: ${\displaystyle n\in \mathbb {N} }$ tal que ${\displaystyle n\geq 3}$ i ${\displaystyle n=F\cdot k+1\,\!}$, on ${\displaystyle F\,\!}$ té una factorització en nombres primers coneguda.

Si per a cada factor primer ${\displaystyle q\,\!}$ de ${\displaystyle F,\;\exists \;a\in \mathbb {N} }$ tal que:

(i) ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

(ii) ${\displaystyle \operatorname {mcd} (a^{\frac {n-1}{q}}-1,n)=1}$.

Llavors ${\displaystyle \forall \;p}$, primer, divisor de n, ${\displaystyle p\equiv 1{\pmod {F}}}$; per tant, si ${\displaystyle F>{\sqrt {n-1}}}$ llavors n és primer.

Així, si es coneix la factorització d'un divisor de F es poden concloure per la comprovació de les condicions (i) i (ii) que un nombre donat és primer. Exemple de prova per Pocklington per al nombre n=57283:

• Se suposa coneguda la factorització parcial n-1 = 6 x 9547 i també conegut el fet que F=9547 és un nombre primer, per tant q és únic i igual a F. Ja que ${\displaystyle 2^{n-1}\equiv 1{\pmod {n}}}$, i ${\displaystyle \operatorname {mcd} (a^{\frac {n-1}{q}}-1,n)=1}$, es pot concloure que n és primer.

L'algorisme és senzill. Es limita a realitzar una sèrie de càlculs amb aritmètica modular i comprovar-ne el resultat. La contrapartida és que es necessita una factorització parcial de n.

L'última prova en aquest apartat es deu a Pepin (1877). El teorema de Pepin s'enuncia com segueix:

Teorema: ${\displaystyle \forall n\in \mathbb {N} }$, el nombre de Fermat enèsim, definit per ${\displaystyle {\mathfrak {F}}_{n}=2^{2^{n}}+1}$ és primer si i nomé si ${\displaystyle 3^{{\mathfrak {F}}_{\frac {n-1}{2}}}\equiv -1{\pmod {{\mathfrak {F}}_{n}}}}$.

La constant 3 de la prova de Pepin en realitat es pot substituir per qualsevol enter positiu per al qual l'operador anomenat símbol de Jacobi sigui igual a -1. Això inclou als valors 3, 5 i 10. Així com la prova de Lucas-Lehmer (LL) només es pot aplicar als nombres de Mersenne, la prova de Pepin només es pot aplicar als nombres de Fermat, pel que el seu ús (com en el cas de LL) queda bastant restringit.

Els tests probabilístics tot i que no proven la primalitat amb total certesa resulten d'interès en tenir un temps de còmput més curt i en ser computacionalment més estables i predictibles.

Si l'nvers del Petit Teorema de Fermat (PTF) fos cert (és a dir, si la comprovació de la condició a^n-1≡1 (mod n), per a qualsevol nombre a primer respecte de n impliqués la primalitat de n) la prova de primalitat seria un assumpte molt senzill. Però, existeix una família de nombres compostos que compleixen la condició, per tant la prova per l'invers del Petit Teorema de Fermat (PTF) no és vàlida; aquest nombres s'anomenen Nombres de Carmichael en honor del matemàtic que els va descobrir. Un exemple de nombre de Carmichael és n=561.

Els test probabilístics estan basats en la idea de relaxar la correcció de la prova per aconseguir un comportament de resposta polinòmic o subpolinòmic. Es basen bé en l'ús del PTF, bé en l'ús dels verificadors i falsadors d'Euler.

El primer exemple de test probabilístic que es veurà és el test de Fermat. L'esmentat test està basat en el PTF. L'algorisme basat en aquest test s'aplica elegint diversos enters aleatoris a entre 2 i n-2 i calculant ${\displaystyle r\equiv a^{n-1}{\pmod {n}}}$. Si algun valor de ${\displaystyle r}$ és diferent d'1 l'algorisme torna compost, en cas contrari torna primer. La fortalesa d'aquest test rau en el fet que després d'un nombre normalment petit de repeticions la probabilitat que un nombre compost passi com a primer és molt petita.

Com s'ha comentat abans, el test de Fermat pateix d'un conegut problema: els nombres de Carmichael. Els nombres de Carmichael passen la condició de Fermat per a tots els possibles valors d'a; això implica que si el candidat a nombre primer fos un nombre de Carmichael, no importa quantes vegades es passi el test de Fermat, el resultat sempre serà negatiu i en conseqüència el resultat del test serà un fals positiu. Tanmateix, els nombres de Carmichael són relativament escassos (n'hi ha 105.212 menors de 10¹⁵) pel que la probabilitat d'elegir-ne algun és realment baixa. El test de Fermat és d'ampli ús en el camp de la criptografia.

Un altre test molt conegut i utilitzat en criptografia és el test de primalitat de Solovay-Strassen (SS). Aquest test està basat en el criteri d'Euler que estableix que si n és un nombre primer senar, llavors ${\displaystyle a^{\frac {(n-1)}{2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$ per a tots els enters que satisfan que el mcd(a, n)=1, on ${\displaystyle \left({\frac {a}{n}}\right)}$ representa el símbol de Jacobi definit per

${\displaystyle \left({\frac {a}{n}}\right)=\prod _{j=1}^{k}\left({\frac {a}{p_{j}}}\right)^{e_{j}}}$

On cada ${\displaystyle p_{j}}$ és un nombre primer diferent, ${\displaystyle e_{j}\in \mathbb {N} }$ i ${\displaystyle \left({\frac {a}{p_{j}}}\right)}$ és el símbol de Legendre definit per

${\displaystyle \left({\frac {c}{p}}\right)={\begin{cases}0&{\mbox{si }}p{\mbox{ divideix a }}c,\\1&{\mbox{si }}c{\mbox{ es residu quadratic modul }}p,\\-1&{\mbox{altrament.}}\end{cases}}}$

Els valors d'a que compleixen el criteri d'Euler s'anomenen verificadors d'Euler per a la primalitat de n i els que no el compleixen es denominen falsadors d'Euler per a la primalitat de n.

El test SS es podria codificar de la següent manera:

Algorisme Test de Solovay-Strassen. (Ordre de complexitat ${\displaystyle {\mathcal {O}}(k\times \log ^{3}n)}$)

Entrada: Un nombre natural n>1, i el nombre k de cops que s'executa el test (i determina la fiabilitat del test). Sortida: COMPOST si n és compost i POSSIBLE PRIMER si no s'ha pogut verificar que n és compost. Fer per a ${\displaystyle j\,\!}$ des de ${\displaystyle 1\,\!}$ fins a ${\displaystyle k\,\!}$ : ${\displaystyle a\gets }$ Funció Genera_nombre_aleatori_en_l'interval_${\displaystyle [2,n-2]\,\!}$ ${\displaystyle r\gets a^{\frac {n-1}{2}}\;{\bmod {\;}}n\,\!}$ Si ${\displaystyle (r\neq 1)\quad \land \quad (r\neq n-1)}$ llavors: retorna COMPOST ${\displaystyle s\gets \left({\frac {a}{n}}\right)}$/*Símbol de Jacobi*/ Si ${\displaystyle \quad r\not \equiv s{\pmod {n}}}$ llavors: Retorna COMPOST Retorna POSSIBLE PRIMER

El test SS té una probabilitat d'encert de ½ per cada pas de j. Això implica que la probabilitat que l'entrada sigui un nombre compost havent estat declarat com a "possible primer" és menor que ½^t. Aquest test va ser descobert el 1978 i va ser modificat el 1982 per Atkin i Larson, però ara com ara està en desús. El motiu és que el test que s'estudia tot seguit és més eficient i, pel cap baix, té el mateix nivell de correcció.

El test més implantat en l'actualitat és el Miller-Rabin (també conegut com a test fort del pseudoprimer). El test de Miller-Rabin (MR) està basat en el següent fet: Si es té un nombre primer n i ${\displaystyle n-1=2^{s}r}$ on r és senar, es compleix que ${\displaystyle \forall \;a\in \mathbb {N} \;/\;{\mbox{mcd}}(a,n)=1}$, llavors o bé ${\displaystyle a^{r}\equiv 1{\pmod {n}}}$ o bé ${\displaystyle \exists j\in [0,s-1]\quad /\quad a^{2^{j}r}\equiv -1{\pmod {n}}}$.

El test MR es pot codificar de la següent manera:

Algorisme Test de Miller-Rabin. (Ordre de complexitat ${\displaystyle {\mathcal {O}}(k\times \log ^{3}n)}$)

Entrada: Un nombre natural n>1, el nombre k de cops que s'executa el test i determina la seva fiabilitat. Sortida: COMPOST si n és compost i POSSIBLE PRIMER si no s'ha pogut verificar que n és compost. Trobar ${\displaystyle r\,\!}$ i ${\displaystyle s\,\!}$ tals que ${\displaystyle r\,\!}$ és senar i ${\displaystyle (n-1)=r\cdot 2^{s}\,\!}$ Fer per a ${\displaystyle j\,\!}$ des de ${\displaystyle 1\,\!}$ fins a ${\displaystyle k\,\!}$ : ${\displaystyle a\gets }$ Funció Genera_nombre_aleatori_en_l'interval ${\displaystyle [2,n-2]\,\!}$ ${\displaystyle y\gets a^{r}\;{\bmod {\;}}n}$ Si ${\displaystyle (y\neq 1)\land (y\neq n-1)}$ llavors: ${\displaystyle j\gets 1\,\!}$ Fer mentre ${\displaystyle j\leq (s-1)\land y\neq (n-1)}$ : ${\displaystyle y\gets y^{2}\;{\bmod {\;}}n\,\!}$ Si ${\displaystyle y=1\,\!}$ llavors: Retorna COMPOST ${\displaystyle j\gets j+1}$ Si ${\displaystyle y\neq (n-1)\,\!}$ llavors: Retorna COMPOST Retorna POSSIBLE PRIMER

L'error comès en cada pas d'iteració és de ¼, (el disseny fa que existeixin més falsadors d'Euler que en SS) pel que la probabilitat que l'entrada sigui un nombre compost quan es declara com a "possible primer" és menor que ¼^t. D'altra banda, en utilitzar l'exponenciació binària les operacions necessàries es realitzen ràpidament.

Dels tres test probabilístics aquí presentats, el millor des del punt de vista tècnic i pràctic és el de Miller-Rabin. El test SS és computacionalment pitjor i més difícil d'implementar, ja que cal calcular el símbol de Jacobi. D'altra banda ambdós tenen l'avantatge davant el de Fermat que es pot augmentar la confiança de la primalitat assignant a t un valor arbitràriament alt (Fermat té el límit definit pels nombres de Carmichael).

Des dels anys 70 s'ha estat treballant en la millora dels algorismes clàssics per obtenir millors proves de primalitat.^[4] Per a això s'ha treballat en la factorització de formes polinòmiques de n. Entre aquests algorismes destaquen el degut a Adleman, Pomerance i Rumely (APR) i la millora que sobre aquest varen fer Cohen i Lenstra (APR-CL) que obtenen complexitats gairebé polinòmiques.

També s'està avançant en aquest camp utilitzant altres formes més senzilles de treball amb grups matemàtics en lloc de l'aritmètica modular dels grups de Galois.

En aquest sentit s'estan fent avenços en el treball amb corbes el·líptiques mòdul n. Una corba el·líptica és una funció que es defineix de la següent forma:

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

En corbes d'aquest tipus han estat treballant des de 1986 Goldwasser, Kilian i Atkin. Aquest últim va definir el mètode ECPP, que té diverses implementacions i que s'ha provat que és d'ordre polinòmic per a gairebé totes les entrades.

Moltes de les proves i tests de primalidad que s'han vist fins ara es resolen en temps polinòmic.

Durant anys els sistemes criptogràfics han estat utilitzant-los per a la generació de claus segures. Tanmateix tenen limitacions. Alguns no són proves de primalidad i en conseqüència no tornen un certificat de primalidad: existeix una probabilitat (encara que petita) de què un nombre sigui considerat primer quan en realitat és compost; són els que es coneixen com a algorismes probabilístics d'ordre P (RP). D'altres sí que certifiquen la primalidad, però no es garanteix que el test acabi en temps polinòmic; són els que es coneixen com a algorismes deterministes de temps polinòmic probabilístic (ZPP). Alguns necessiten factoritzacions parcials o totals de n+1 i, com ja s'ha vist, la factorització és un problema que no es pot resoldre en temps polinòmic en el cas general. Per a d'altres, l'acabament en temps polinòmic es basa en certes conjectures no provades.

Per exemple, el test de Miller és polinòmic si la hipòtesi estesa de Riemann (o conjectura ERH) és certa. Hi ha una creença generalitzada en la conjectura ERH, però en faltar una demostració matemàtica no es pot concloure el seu acabament polinòmic.

El recent descobriment d'un algorisme determinista de temps polinòmic que no es basa en cap conjectura no provada ha de ser considerat una fita important. Concretament l'agost de l'any 2002 tres acadèmics de la Universitat de Kanpur (Agrawal, Kayal i Saxena) varen presentar^[5] un algorisme determinista de classe P per a la determinació de la primalitat d'un nombre. La clau de l'algorisme és una versió simplificada del PTF això és la condició:

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

Els autors se les varen arreglar per a formular el següent algorisme, que s'ha provat que pot executar-se en un temps de complexitat màxima de ${\displaystyle {\mathcal {O}}((\log \,n)^{12}f(\log \;\log \,n))}$.

Algorisme Prova de primalitat AKS. (Ordre de complexitat ${\displaystyle {\mathcal {O}}((\log \,n)^{12+\epsilon })}$)

Entrada: Un nombre natural n > 1. Sortida: COMPOST si n és compost y PRIMER si n és primer. Si existeixen ${\displaystyle a,b\in \mathbb {N} ,\,b>1}$ tals que ${\displaystyle n=a^{b}\,\!}$ llavors: Retorna COMPOST ${\displaystyle r\gets 2}$ Fer mentre ${\displaystyle r<n\,\!}$ : Si ${\displaystyle {\mbox{mcd}}(n,r)\neq 1}$ llavors: Retorna COMPOST. Si ${\displaystyle r\,\!}$ és primer > 2 llavors: ${\displaystyle q\gets }$ Factor més gran de ${\displaystyle r-1\,\!}$ Si ${\displaystyle q\geq 4{\sqrt {r}}\log _{2}(n)\;\land \;n^{\frac {(r-1)}{q}}\not \equiv 1{\pmod {r}}}$ llavors: Fi mentre ${\displaystyle r\gets r+1}$ Fer per ${\displaystyle a=1\,\!}$ fins a ${\displaystyle 2{\sqrt {r}}\log _{2}n}$ : Si ${\displaystyle (x-a)^{n}\not \equiv (x^{n}-a){\pmod {x^{r}-1,\,n}}}$ llavors: Retorna COMPOST Retorne PRIMO

Els autors varen demostrar a més, que si determinats nombres primers (anomenats nombres primers de Sophie Germain) tenen la distribució conjecturada per Ardí, l'exponent 12 que apareix en l'expressió de complexitat pot reduir-se a 6. El que implica que el temps estimat d'execució seria equivalent al d'alguna test de primalidad, com ara el mètode ECPP comentat més amunt, que es basa en les corbes el·líptiques.

En realitat aquest descobriment no té implicacions pràctiques en la computació moderna. El cert és que les parts constants de la complexitat de l'algorisme són molt més costoses que en els actuals algorismes probabilístics. És d'esperar que en el futur proper s'obtinguin millores en aquestes constants, però el cert és que els algorismes actuals de generació de nombres primers cobreixen bastant bé les necessitats actuals i, possiblement, les futures (i és poc probable que la línia proposada millori en temps d'execució als algorismes probabilístics existents). Tanmateix sí que té una importància fonamental des del punt de vista teòric, ja que suposa la primera prova de primalitat d'aquestes característiques que s'ha demostrat matemàticament.

• 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.) (anglès)
• Crandall, Richard & Pomerance, Carl: Prime Numbers: A Computational Perspective Capítol 3: "Recognizing Primes and Composites", pp.109–158. Capítol 4: "Primality Proving", pp.159–190. Secció 7.6: "Elliptic curve primality proving (ECPP)", pp.334–340. Springer, 1a edició, 2001. (ISBN 0-387-94777-9.) (anglès)
• Knuth, Donald. The Art of Computer Programming, Volum 2: Seminumerical Algorithms. Pàgines 391–396 de secció 4.5.4. Addison-Wesley, 3a edició, 1997. (ISBN 0-201-89684-2.) (anglès)
• Williams, H.C.: Édouard Lucas and Primality Testing. John Wiley & Sons, 1998. (ISBN 0-471-14852-0.) (anglès)

• Complexitat computacional
• Criptografia
• Édouard Lucas
• Petit teorema de Fermat

En català

• Facultat d'informàtica de Barcelona: Primalitat Arxivat 2009-12-17 a Wayback Machine.
• Publicacions de l'Institut d'Estudis Catalans: L'algorisme de primalitat AKS

En anglès

• Agrawal, Kayal & Saxena: Primes is in P Arxivat 2005-05-12 a Wayback Machine. Instituto de Tecnología Kanpur, India.
• Bernstein, D.J.: Distinguishing prime numbers from composite numbers
• Caldwell, Chris: The Prime Pages Universitat de Tennessee.