Testul Fermat se bazează pe un rezultat din teoria numerelor cunoscută sub numele de teorema mică a lui Fermat.

Conform teoremei mici a lui Fermat, dacă n este un număr prim și d este orice număr întreg pozitiv mai mic decât n, atunci d ridicat la a n-a puterea este congruentă cu d modulo n.

Dacă două numere au același rest atunci când sunt împărțite la n atunci se spune că sunt congruent modulo n. d modulo n este pur și simplu restul unui număr d când este împărțit la n.

De exemplu, 34 este congruent cu 16 (modulo 3) ca
34 modulo 3 = 1 și 16 modulo 3 = 1.

Testul Fermat pentru primalitate

  1. Pentru un număr dat n, alegeți un număr pozitiv aleatoriu d astfel încât d <; n.
  2. calculati (d ^ n) modulo n.
  3. d modulo n va fi întotdeauna d după cum alegem întotdeauna d care satisface condiția d <; n.
  4. Dacă rezultatul (d ^ n) modulo n nu este egal cu d, atunci d cu siguranță nu este prim.
  5. Dacă rezultatul (d ^ n) modulo n este egal cu d, atunci sunt mari șanse ca. n este prim.
  6. Alegeți o altă întâmplare d care satisface condiția d < n și repetați pașii de mai sus.

Notă: Exemplele din acest post sunt folosite Swift 4.1

Avem nevoie de o funcție pentru a calcula exponențialul unui număr modulo un alt număr.

ad-banner
Cum se executa testul Fermat pentru primalitate in mai putin
Calculați (d ^ n) modulul n

Folosim exponențierea modulară pentru a calcula valori atunci când exponentul este mai mare de 1 deoarece acest lucru ne permite să efectuăm calcule în timp ce avem de-a face doar cu numere mai mici de n (modulo în funcția de mai sus).

1611276005 15 Cum se executa testul Fermat pentru primalitate in mai putin
Testul Fermat

Testul Fermat alege la întâmplare un număr d între 1 și n-1 (Numărul 1 în funcția de mai sus) inclusiv. Scopul este de a verifica dacă restul modulului n al puterii a n-a lui d este egal cu d.

1611276006 682 Cum se executa testul Fermat pentru primalitate in mai putin
Rulați testul Fermat pentru numărul specificat

Testul Fermat se execută pentru numărul specificat. Dacă un număr nu reușește testul Fermat, suntem siguri că nu este prim. Dacă un număr trece testul Fermat, nu este garantat să fie prim. Încercăm să reducem probabilitatea de eroare în testul nostru de primalitate prin rularea testului de suficiente ori.

Încercând din ce în ce mai multe valori ale d (un număr pozitiv aleatoriu între 1 și n-1), ne putem crește încrederea în rezultat.