Priemtest van Fermat

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Fermattest)
Ga naar: navigatie, zoeken

De priemtest van Fermat is een probabilistische methode om te testen of een getal waarschijnlijk priem is.

Theorie[bewerken]

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

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

Wanneer we willen testen of een getal p priem is, kiezen we willekeurige getallen 1 ≤ a < p en controleren of bovenstaande equivalentie geldt. De equivalentie geldt voor alle priemgetallen, dus als het niet geldt voor een zekere waarde van a, dan is p samengesteld. Als er veel waarden van a zijn waarvoor de equivalentie wel geldt, dan kunnen we zeggen dat p waarschijnlijk priem is, of een pseudopriemgetal (een samengesteld getal dat eigenschappen heeft die alle priemgetallen ook hebben).

Aangezien we a willekeurig kiezen, is het mogelijk dat voor geen enkele a die we kiezen de equivalentie niet geldt. Als n een samengesteld getal is, dan wordt elke a waarvoor:

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

een Fermat-leugenaar genoemd. Als we een a kiezen zodanig dat:

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

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

Voorbeeld[bewerken]

Stel dat we willen bepalen of n = 221 priem is. Kies een willekeurige 1 ≤ a < 221 van a = 38. Controleer bovenstaande equivalentie:

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 221 is samengesteld en 38 was inderdaad een Fermat-leugenaar.

Algoritme[bewerken]

Het algoritme kan in pseudocode als volgt worden opgesteld:

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.

Hiaten in de test[bewerken]

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 c een pseudopriemgetal (ac−1 ≡ 1 (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.[1]

Nauwkeurigheid[bewerken]

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. Dit is als volgt te bewijzen: laat {a1, a2, ..., am} de Fermat-leugenaars zijn en a een Fermat-getuige. Dan geldt voor i = 1,2,...,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 elke ai geeft een getal a·ai, dat ook een Fermat-getuige is. Oftewel elke Fermat-leugenaar geeft een Fermat-getuige en dus is het aantal Fermat-getuigen groter dan of gelijk aan het aantal Fermat-leugenaars. Hiermee volgt dat wanneer n samengesteld is en geen Carmichael-getal, dan zijn ten minste de helft van alle a Fermat-getuigen.

Externe link[bewerken]

Referenties[bewerken]

  1. W. R. Alford, A. Granville, and C. Pomerance. "There are Infinitely Many Carmichael Numbers." Annals of Mathematics 139 (1994) 703-722. (en)
Bronnen, noten en/of referenties