Kuidas käivitada Fermati test primaarsuse jaoks vähem kui 3 minutiga

Fermati test põhineb Fermati väikese teoreemina tuntud arvuteooria tulemusel.

Fermati väikese teoreemi kohaselt, kui n on algarv ja d on positiivne täisarv, mis on väiksem kui n , siis n-nda astmeni tõstetud d on d mooduliga n ühtne .

Kui kahel arvul on n-ga jagatuna sama jääk, siis öeldakse, et need on ühtsed moodulid n . d moodul n on lihtsalt arvu d järelejäänud osa jagatuna n-ga .

Näiteks on 34 võrdne 16-ga (moodul 3) kui

34 moodul 3 = 1 ja 16 moodul 3 = 1.

Fermati test primaarsuse jaoks

  1. Antud arvu n jaoks vali juhuslik positiivne arv d, nii et d < ; n.
  2. Arvutage (d ^ n) moodul n .
  3. d moodul n on alati d, kuna me valime alati d, mis vastab tingimusele d < ; n.
  4. Kui (d ^ n) mooduli n tulemus ei ole võrdne d-ga , siis pole d kindlasti algarv.
  5. Kui (d ^ n) mooduli n tulemus on võrdne d-ga , on tõenäosus, et n on peamine.
  6. Valige veel üks juhuslik d, mis vastab tingimusele d < n, ja korrake ülaltoodud samme.

Märkus . Selle postituse näited kasutavad Swift 4.1

Vajame funktsiooni, et arvutada eksponentsiaal arvule teine ​​arv.

Väärtuste arvutamiseks kasutame modulaarset eksponentimist, kui eksponent on suurem kui 1, kuna see võimaldab meil arvutada, tegeledes ainult arvudega, mis on väiksemad kui n ( moodul ülaltoodud funktsioonis).

Fermati test valib juhuslikult arvu d vahemikus 1 kuni n-1 ( arv - 1 ülaltoodud funktsioonis) (kaasa arvatud). Eesmärk on kontrollida, kas d-nda võimsuse ülejäänud modulo n on võrdne d-ga.

Fermati test viiakse läbi määratud loendusega. Kui number ei läbi Fermati testi, oleme kindlad, et see pole algarv. Kui number läbib Fermati testi, pole see garanteeritud algarv. Proovime oma esmatestis vähendada vea tõenäosust, käivitades testi piisavalt palju kordi.

Proovides üha uusi d väärtusi (juhuslik positiivne arv vahemikus 1 kuni n-1), saame suurendada oma usaldust tulemuse suhtes.