Priemtest van Fermat

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

Theorie

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