Test de primalitat de Fermat

De Viquipèdia
Salta a la navegació Salta a la cerca

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

Concepte[modifica]

El petit teorema de Fermat estableix que si p és primer i , llavors

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 molts 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

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

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

Algorisme i temps d'execució[modifica]

L'algorisme es pot escriure tal com segueix:

Algorisme test de primalitat de Fermat (Ordre de complexitat )

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.

  1. Fer per a des de fins :
    1. Funció Genera_nombre_aleatori_en_interval
    2. Si llavors:
      1. Retorna COMPOST
  2. 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 × log2n × 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[modifica]

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 ha prou perquè el test de primalitat de Fermat sovint no es faci servir en favor d'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

són Fermat testimonis. Per demostrar-ho, sia a un Fermat testimoni i a1, a2, ..., as siguin Fermat mentiders. Llavors

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

Utilització[modifica]

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

Referències[modifica]