Priemtest van Fermat

De priemtest van Fermat is een probabilistische methode om te controleren dat een getal een priemgetal is. De methode geeft geen uitsluitsel, maar alleen een indicatie dat het waarschijnlijk is dat het een priemgetal is.

Theorie

De test is gebaseerd op de kleine stelling van Fermat. Voor een priemgetal $p$ en $1\leq a<p$ geldt:

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

Om te testen of een getal $p$ priem is, kiest men willekeurige getallen $1\leq a<p$ en gaat na of de kleinse stelling van Fermat daarvoor geldt. De vergelijking geldt voor alle priemgetallen, dus als het niet geldt voor een zekere waarde van $a$, is $p$ een samengesteld getal. Als er veel waarden van $a$ zijn waarvoor de vergelijking wel geldt, kan men zeggen dat $p$ waarschijnlijk een priemgetal is, of een pseudopriemgetal.

Aangezien $a$ willekeurig is gekozen, kan het zijn dat voor geen enkele gekozen $a$ de vergelijking niet geldt. Is $n$ een samengesteld getal, dan wordt elke $a$ waarvoor:

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

een Fermat-leugenaar genoemd. Kiest men $a$ zodanig dat:

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

dan wordt $a$ een Fermat-getuige genoemd van het feit dat $n$ een samengesteld getal is.

Voorbeeld

Stel dat we willen bepalen of $n=221$ een priemgetal is. Kies een willekeurige 1 ≤ $a$ < 221 van $a$ = 38. Controleer de bovenstaande vergelijking:

$a^{n-1}=38^{220}\equiv 1{\pmod {221}}$

Ofwel 221 is priem, ofwel 38 is een Fermat-leugenaar. Daarom kiezen we een andere $a$ van 26:

$a^{n-1}=26^{220}\equiv 169\not \equiv 1{\pmod {221}}$

Dus is 221 samengesteld en was 38 inderdaad een Fermat-leugenaar.

Algoritme

Het algoritme kan in pseudocode als volgt worden geschreven:

Invoer: n > 1, waarvan getest moet worden of het al dan niet priem is; k, een geheel getal, dat de nauwkeurigheid van de test bepaalt
Uitvoer: samengesteld als n samengesteld is, anders is mogelijk priem. 
herhaal k keer:
   neem een willekeurige a uit (1, n−1]
   als ggd(a,n) $\neq$ 1, dan uitvoer samengesteld
   als an−1 $\not \equiv$1 (mod n), dan uitvoer samengesteld
uitvoer mogelijk priem.

Opmerkingen

• De priemtest van Fermat is niet waterdicht. Een belangrijk probleem voor de test wordt gevormd door een speciaal soort samengestelde getallen, de carmichael-getallen. Dit zijn de samengestelde getallen $c$ met de eigenschap dat $a^{c-1}\equiv 1\ (\mathrm {mod} \ c)$ is voor elke $a$ met ggd($a$,$c$) = 1. Tevens geldt dat elke vermenigvuldiging van $c$ zelf ook een pseudopriemgetal is. Er is een oneindig aantal originele carmichael-getallen.

• Wanneer $n$ een samengesteld getal is, dat geen carmichael-getal is, dan geldt dat ten minste de helft van alle

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

Fermat-getuigen zijn.

Bewijs 

Laat $\{a_{1},a_{2},\ldots ,a_{m}\}$ de Fermat-leugenaars zijn en $a$ een Fermat-getuige. Dan geldt voor $i=1,\ldots ,m$ dat:

$(a\cdot a_{i})^{n-1}=a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\cdot 1\equiv a^{n-1}\not \equiv 1{\pmod {n}}$

Dus geeft elke $a_{i}$ een getal $a\cdot a_{i}$, dat ook een Fermat-getuige is. Oftewel geeft elke Fermat-leugenaar een Fermat-getuige, dus is het aantal Fermat-getuigen groter dan of gelijk aan het aantal Fermat-leugenaars. Hiermee volgt dat wanneer $n$ samengesteld en geen carmichael-getal is, dat ten minste de helft van alle $a$ Fermat-getuigen zijn.