Kuinka suorittaa Fermat-testi ensisijaisuudelle alle 3 minuutissa

Fermat-testi perustuu lukuteorian tulokseen, joka tunnetaan nimellä Fermatin pieni lause.

Fermatin pienen lauseen mukaan, jos n on alkuluku ja d on mikä tahansa positiivinen kokonaisluku, joka on pienempi kuin n , niin n: nneksi tehoksi nostettu d on yhtenevä d modulo n: n kanssa .

Jos kahdella luvulla on sama loppuosa jaettuna n: llä, niiden sanotaan olevan yhtäpitäviä modulo n . d modulo n on yksinkertaisesti luvun d loppuosa jaettuna n: llä .

Esimerkiksi 34 on yhtäpitävä arvoon 16 (moduuli 3) kuin

34 moduuli 3 = 1 ja 16 moduuli 3 = 1.

Fermat-testi ensisijaisuudesta

  1. Annetulle luvulle n valitse satunnainen positiivinen luku d siten, että d < ; n.
  2. Laske (d ^ n) moduuli n .
  3. d modulo n tulee olemaan aina d, koska valitsemme aina d, joka täyttää ehdon d < ; n.
  4. Jos (d ^ n) modulo n: n tulos ei ole yhtä suuri kuin d , d ei todellakaan ole alkuluku.
  5. Jos (d ^ n) modulo n: n tulos on yhtä suuri kuin d , on todennäköistä, että n on prime.
  6. Valitse toinen satunnainen d, joka täyttää ehdon d < n, ja toista yllä olevat vaiheet.

Huomaa : Tämän viestin esimerkit käyttävät Swift 4.1: tä

Tarvitsemme funktion, jotta voimme laskea luvun eksponentin modulo toisen luvun.

Käytämme modulaarista eksponentointia arvojen laskemiseen, kun eksponentti on suurempi kuin 1, koska tämä antaa meille mahdollisuuden suorittaa laskenta samalla kun käsittelemme vain alle n lukuja ( modulo yllä olevassa funktiossa).

Fermat-testi valitsee satunnaisesti luvun d välillä 1 ja n-1 ( luku - 1 yllä olevassa funktiossa) mukaan lukien. Tavoitteena on tarkistaa, onko d: n n: n potenssin loppuosa modulo n yhtä suuri kuin d.

Fermat-testi suoritetaan määritetylle määrälle. Jos luku epäonnistuu Fermat-testissä, voimme olla varmoja, että se ei ole ensisijainen. Jos numero läpäisee Fermat-testin, sen ei voida taata olevan prime. Yritämme vähentää virheen todennäköisyyttä alkutestissä suorittamalla testi riittävän monta kertaa.

Kokeilemalla yhä useampia d: n arvoja (satunnainen positiivinen luku välillä 1 ja n-1) voimme lisätä luottamustamme tulokseen.