miniatura|El 39è nombre primer de Mersenne. 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 primeritatTermcat (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).
Motivació El problema de la Factorització és un problema per al qual no s'ha trobat una solució de Temps polinòmic.Papadimitriou, Christos H.: Computational Complexity. Sección 10.2: "Primality", pp.222–227. Addison-Wesley, 1.ª edición, 1993. (.)
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:
On é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 é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:
Aquesta probabilitat és força gran, fins i tot per a nombres molt grans, per exemple la probabilitat que un nombre entre i 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.
Història del problema de la primalitat 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 () encara que hi ha evidències que el coneixement de l'existència d'aquests nombres es remunta a Pitàgores (). 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 donat, primer es col·loquen els nombres de l'1 a l' 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 s'atura l'algorisme. Els nombres que han quedat sense ratllar, són tots els nombres primers més petits que .
La versió original de l'algorisme del garbell d'Erastòstenes no s'acabava en . 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 divideix a . 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 és primer llavors ha de ser primer i 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 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 per a p =2, 3, 5, 7, 13, 17, 19, 31, 67, 127 i 257). De fet Mersenne va cometre alguns errors perquè 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 és primer, llavors quealsevol nombre primer que divideixi a ha de ser de la forma per algun . També es pot demostrar que si és el nombre més petit tal que , llavors sempre que .
Fermat s'adonà que el teorema anterior era útil para a detectar possibles nombres primers tales que . Fermat també va suggerir que els nombres de la forma (anomenats nombres de Fermat i representats per ) 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 i avui se sap que és compost, com ho són tots fins a (i potser tots els altres, tot i que això encara és una conjectura).
Leonhard Euler va trobar un divisor de (contradient la conjectura de Fermat sobre la primalitat de ). Va enunciar el teorema que diu que tot divisor primer de ha de ser de la forma per a algun .
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 ).
Definicions de Test de primalitat i de prova de primalitat 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 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).
Test verdaders de primalitat Tot seguit s'estudien les proves de primalitat.
Prova de Lucas-Lehmer per a nombres de Mersenne 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:
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.
Prova basada en el teorema de Pocklington 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.Caldwell, Chris,Finding primes & proving primality Dit teorema estableix el següent:
Teorema: tal que i , on té una factorització en nombres primers coneguda.
Si per a cada factor primer de tal que:
(i) (ii) . Llavors , primer, divisor de n, ; per tant, si 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 , i , 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.
Prova basada en el teorema de Pepin L'última prova en aquest apartat es deu a Pepin (1877). El teorema de Pepin s'enuncia com segueix:
Teorema: , el nombre de Fermat enèsim, definit per és primer si i nomé si . 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.