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 , 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.