Sådan køres Fermat-testen for primalitet på under 3 minutter

Fermat-testen er baseret på et resultat fra talteori kendt som Fermats lille sætning.

Ifølge Fermats lille sætning, hvis n er et primtal og d er et hvilket som helst positivt heltal mindre end n , så er d hævet til den nte styrke kongruent til d modulo n .

Hvis to tal har den samme rest, når de divideres med n , siges de at være kongruente modulo n . d modulo n er simpelthen resten af ​​et tal d divideret med n .

For eksempel er 34 kongruent til 16 (modulo 3) som

34 modulo 3 = 1 og 16 modulo 3 = 1.

Fermat test for primalitet

  1. For et givet tal n skal du vælge et tilfældigt positivt tal d således at d < ; n.
  2. Beregn (d ^ n) modulo n .
  3. d modulo n vil altid være d, da vi altid vælger d, der opfylder betingelsen d < ; n.
  4. Hvis resultatet af (d ^ n) modulo n ikke er lig med d , så er d bestemt ikke prime.
  5. Hvis resultatet af (d ^ n) modulo n er lig med d , så er chancerne gode for, at n er prime.
  6. Vælg en anden tilfældig d, der opfylder betingelsen d < n, og gentag ovenstående trin.

Bemærk : Eksemplerne i dette indlæg bruger Swift 4.1

Vi har brug for en funktion til at beregne den eksponentielle af et tal modulo et andet tal.

Vi bruger modulær eksponentiering til at beregne værdier, når eksponenten er større end 1, da dette giver os mulighed for at udføre beregning, mens vi kun beskæftiger os med tal mindre end n ( modulo i ovenstående funktion).

Fermat-testen vælger tilfældigt et tal d mellem 1 og n-1 ( nummer - 1 i ovenstående funktion) inklusive. Målet er at kontrollere, om den resterende modulo af den nte effekt af d er lig med d.

Fermat-testen køres for det angivne antal. Hvis et tal ikke består Fermat-testen, er vi sikre på, at det ikke er prime. Hvis et tal består Fermat-testen, er det ikke garanteret at være prime. Vi prøver at reducere sandsynligheden for fejl i vores primality test ved at køre testen nok gange.

Ved at prøve flere og flere værdier af d (et tilfældigt positivt tal mellem 1 og n-1) kan vi øge vores tillid til resultatet.