Kaip atlikti „Fermat“ testą dėl pirmumo per mažiau nei 3 minutes

„Fermat“ testas pagrįstas skaičių teorijos, vadinamos mažąja Fermato teorema, rezultatu.

Remiantis mažąja Fermato teorema, jei n yra pagrindinis skaičius ir d yra bet kuris teigiamas sveikasis skaičius, mažesnis už n , tada d, pakeltas iki n-tosios galios, sutampa su d moduliu n .

Jei du skaičiai turi tą patį likutį, padalijant iš n , sakoma, kad jie yra sutampantys modulo n . d modulo n yra tiesiog likusi skaičiaus d dalis , padalyta iš n .

Pavyzdžiui, 34 sutampa su 16 (modulo 3) kaip

34 modulis 3 = 1 ir 16 modulis 3 = 1.

Fermat testas dėl pirmumo

  1. Nurodytam skaičiui n pasirinkite atsitiktinį teigiamą skaičių d , kad d < ; n.
  2. Apskaičiuokite (d ^ n) modulo n .
  3. d modulo n visada bus d, nes mes visada pasirenkame d, kuris tenkina sąlygą d < ; n.
  4. Jei (d ^ n) modulio n rezultatas nėra lygus d , tai d tikrai nėra pirminis.
  5. Jei (d ^ n) modulio n rezultatas yra lygus d , tada didelė tikimybė, kad n yra pagrindinis.
  6. Pasirinkite kitą atsitiktinį d, kuris tenkina sąlygą d < n, ir pakartokite aukščiau nurodytus veiksmus.

Pastaba : Šio įrašo pavyzdžiuose naudojama „Swift 4.1“

Mums reikia funkcijos skaičiaus eksponentui apskaičiuoti modulo kitą skaičių.

Mes naudojame modulinį eksponavimą skaičiuojant vertes, kai rodiklis yra didesnis nei 1, nes tai leidžia mums atlikti skaičiavimus, kai kalbama tik apie mažesnius nei n skaičius ( aukščiau nurodytos funkcijos modulis ).

„Fermat“ testas atsitiktinai parenka skaičių d nuo 1 iki n-1 ( skaičius - 1 pirmiau pateiktoje funkcijoje) imtinai. Tikslas yra patikrinti, ar likusi d-osios galios modulo n yra lygi d.

Fermat testas atliekamas nurodytu skaičiumi. Jei skaičius neatitinka Fermat testo, mes esame tikri, kad jis nėra pagrindinis. Jei skaičius išlaikys „Fermat“ testą, jis nėra garantuotas. Mes bandome sumažinti klaidos tikimybę atlikdami pirmumo testą, atlikdami testą pakankamai kartų.

Išbandę vis daugiau d reikšmių (atsitiktinis teigiamas skaičius tarp 1 ir n-1), galime padidinti pasitikėjimą rezultatu.