Test de primalitat de Fermat

El test de primalitat de Fermat és un algorisme aleatori per a determinar si un nombre és un nombre primer probable.

Concepte

El petit teorema de Fermat estableix que si p és primer i $1 \le a < p$, llavors

$a^{p-1} \equiv 1 \pmod{p}$

Si es vol provar si p és primer, llavors es pot triar un nombre aleatori a en l'interval i veure si la igualtat es compleix. Si la igualtat no es compleix per a qualsevol valor de a, llavors p és compost. Si la igualtat no es compleix per a mols valors de a, llavors es pot dir que p és un nombre primer probable, o un pseudoprimer.

Pot ser que els tests que es facin no es triï cap valor de a tal que la igualtat falli. De qualsevol a tal que

$a^{n-1} \equiv 1 \pmod{n}$

quan n és compost es diu que és un Fermat mentider. Si es tria un a tal que

$a^{n-1} \not\equiv 1 \pmod{n}$

llavors es diu que a és un Fermat testimoni de què n és compost.

Algorisme i temps d'execució

L'algorisme es pot escriure tal com segueix:

Algorisme test de primalitat de Fermat (Ordre de complexitat $\mathcal O(k \times (\log n)^{2+\epsilon})$)

Entrada: Un nombre natural n>1, el nombre k de cops que s'executa el test i que determina la seva fiabilitat. Sortida: COMPOST si n és compost y POSSIBLE PRIMER si n és un nombre primer probable. Fer per a $j\,\!$ des de $1\,\!$ fins $k\,\!$ : $a \gets$ Funció Genera_nombre_aleatori_en_interval$(1,n-1]\,\!$ Si $a^{n-1} \not \equiv 1 \pmod n$ llavors: Retorna COMPOST Retorna POSSIBLE PRIMER

Si es fa servir algorismes ràpids per a la exponenciació modular, el temps d'execució d'aquest algorisme és O(k × log²n × log log n × log log log n), on k és el nombre de cops que es tria un nombre aleatori a, i n és el nombre que es vol provar per a veure si és o no primer.

Comentaris

Hi ha certs valors de n coneguts com a nombres de Carmichael per als quals tots els valors de a per als quals el mcd(a,n)=1 són Fermat mentiders. Tot i que els nombres de Carmichael són rars, n'hi h prous com per que el test de primalitat de Fermat sovint no es faci servir en favor de altres tests de primalitat tal com el de Miller-Rabin i el de Solovay-Strassen.

En general, si n no és un nombre de Carmichael llavors pel cap baix la meitat de tots els

$a\in(\mathbb{Z}/n\mathbb{Z})^*$

són Fermat testimonis. Per demostrar-ho, sia a un Fermat testimoni i a₁, a₂, ..., a_s siguin Fermat mentiders. Llavors

$(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}$

I així tot a × a_i per i = 1, 2, ..., s són Fermat testimonis.

Utilització

El programa de xifratge PGP fa servir aquest test de primalitat en els seus algorismes. La possibilitat de què PGP generi un nombre de Carmichael és inferior a 1 en 10⁵⁰, que és més que adequat per aplicacions pràctiques.

Referències

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 889–890 of section 31.8, Primality testing.