În algoritmică , testul de primărie Fermat este un test de primărie probabilist bazat pe mica teoremă a lui Fermat . Este de tip Monte-Carlo : dacă detectează că un număr este compus, atunci are dreptate; pe de altă parte, poate fi greșit dacă pretinde că numărul este prim.
Teorema mică a lui Fermat este enunțată în termeni de congruență asupra numerelor întregi :
Teorema - dacă p este un număr prim atunci pentru toate , (adică este divizibil cu p )
Reciproca teoremei este adevărată: într - adevăr, în cazul în care nu prim, ia în considerare o divizorul non-trivială a . Avem și, pentru toate , este divizibil prin , prin urmare , prin urmare .
Pe de altă parte, dacă fixăm baza , este posibil ca fără a fi prim; se spune că un astfel de număr este pseudo-primul Fermat de bază . Conform observației anterioare, nu există niciun număr care să fie pseudo-primul lui Fermat pentru nicio bază .
O consecință a teoremei lui Fermat este că, atunci când este primă, pentru orice . De data aceasta, conversa este falsă, de exemplu: nu este primă și totuși, pentru orice număr întreg a < 561 , avem . Numerele p care determină eșecul conversației se numesc numere Carmichael și formează un set infinit.
Testul primality Fermat se bazează pe următoarea idee: dacă p este compus, atunci este puțin probabil ca o p -1 este congruent cu 1 modulo p pentru o valoare arbitrară a unui . Iată un pseudo-cod pentru testul Fermat, așa cum este prezentat de Dasgupta și colab. :
fonction testPrimaliteFermat(N) choisir un entier positif a < N au hasard si aN-1 ≡ 1 mod N alors retourner oui (N est probablement premier) sinon retourner non (N est composé)Calculul unui N-1 se face cu un algoritm modular de exponențiere . Cormen și colab. (vezi p. 889 din) dă algoritmului doar pentru a = 2 și numește pseudo-primul bazei 2 un număr N care trece următorul test:
fonction testPrimaliteFermat2(N) si 2N-1 ≡ 1 mod N alors retourner oui (N est probablement premier) sinon retourner non (N est composé)Pentru testul testPrimaliteFermat2 (numai cu a = 2), există doar 22 de valori de N mai mici de 10.000 pentru care testul este greșit. Primele valori sunt 341, 561, 645 și 1105 ( A001567 , vezi p. 890 in). Probabilitatea ca acest algoritm să facă o eroare pe un număr întreg N tinde spre 0 atunci când numărul de biți de N tinde spre 0 (vezi p. 890 în). Pomerance a studiat o estimare exactă a numerelor pseudo-prime ale lui Fermat, pe care Cormen și colab. (vezi p. 890 în) rezumat de:
Pentru testul testPrimaliteFermat, dacă un număr N eșuează testul Fermat pentru o anumită valoare a, atunci eșuează pentru cel puțin jumătate din opțiunile lui a (cf. p. 26 în). Pentru a vedea acest lucru, luați în considerare setul B al valorilor a care nu eșuează, adică B = {a: a N-1 ≡ 1 mod N}. Avem | B | <N-1. Este un subgrup strict al grupului multiplicativ . Prin teorema lui Lagrange , . Astfel, iterând k ori testul Fermat în felul următor, probabilitatea de a returna „da” dacă N este compus este mai mică de 1/2 k .
fonction testPrimaliteFermatItere(N) choisir k entiers positifs a1, ... ak < N au hasard si aiN-1 ≡ 1 mod N pour tout i = 1, ..., k alors retourner oui (N est probablement premier) sinon retourner non (N est composé)Dasgupta și colab. (cf. p. 28 in) argumentează faptul că se folosește un test de primalitate pentru a genera numere prime.
La fiecare iterație, există 1 / n șansă de oprire. Astfel, procedura se oprește în pași O (n). Potrivit lui Dasgupta și colab. (cf. p. 30 in), testul lui Fermat cu a = 2 face posibilă generarea numerelor prime, cu o eroare de 10 -5 pentru numerele N <25 × 10 9 .
Software-ul de criptare Pretty Good Privacy (PGP) profită al acestei proprietăți a teoremei pentru a examina dacă numerele aleatoare mari pe care le alege sunt prime. Acesta examinează valorile pe care le vom numi x folosind patru valori ale unui (numite martori) folosind formula de mai sus. Aceste patru valori sunt 2 , 3 , 5 și 7 , primele patru numere prime.
da
, atunci știm că numărul x este probabil prim .Dacă oricare dintre aceste ecuații dă o valoare diferită de 1, atunci x este cu siguranță compozit . Utilizarea cookie-urilor suplimentare scade șansa ca un număr compus x să fie considerat prim, deși foarte puține numere mari pot păcăli toate cele 4 cookie-uri.