Priemtest van Fermat
De priemtest van Fermat is een probabilistische methode om te testen of een getal waarschijnlijk priem is.
Theorie
bewerkenDe test is gebaseerd op de kleine stelling van Fermat, die luidt: Voor een priemgetal en geldt:
Om te testen of een getal priem is, kiest men willekeurige getallen en gaat na of bovenstaande equivalentie geldt. De equivalentie geldt voor alle priemgetallen, dus als het niet geldt voor een zekere waarde van , is samengesteld. Als er veel waarden van zijn waarvoor de equivalentie wel geldt, kan men zeggen dat waarschijnlijk priem is, of een pseudopriemgetal (een samengesteld getal dat eigenschappen heeft die alle priemgetallen ook hebben).
Aangezien willekeurig gekozen is, kan het zijn dat voor geen enkele gekozen de equivalentie niet geldt. Is een samengesteld getal, dan wordt elke waarvoor:
een Fermat-leugenaar genoemd. Kiest men zodanig dat:
dan wordt een Fermat-getuige genoemd van het feit dat samengesteld is.
Voorbeeld
bewerkenStel dat we willen bepalen of n = 221 priem is. Kies een willekeurige 1 ≤ a < 221 van a = 38. Controleer bovenstaande equivalentie:
Ofwel 221 is priem, ofwel 38 is een Fermat-leugenaar; daarom kiezen we een andere a van 26:
Dus 221 is samengesteld en 38 was inderdaad een Fermat-leugenaar.
Algoritme
bewerkenHet 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) 1, dan uitvoer samengesteld als an−1 1 (mod n), dan uitvoer samengesteld uitvoer mogelijk priem.
Hiaten in de test
bewerkenDe 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
bewerkenWanneer n een samengesteld getal is, dat geen Carmichael-getal is, dan geldt dat ten minste de helft van alle
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:
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
bewerkenReferenties
bewerken- ↑ W. R. Alford, A. Granville, and C. Pomerance. "There are Infinitely Many Carmichael Numbers." Annals of Mathematics 139 (1994) 703-722. (en)
- Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Fermat_primality_test op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.