Hogyan lehet a Fermat-tesztet futtatni 3 perc alatt

A Fermat-teszt a Fermat kis tételének nevezett számelmélet eredményén alapul.

Fermat kis tételének megfelelően, ha n prímszám és d bármely pozitív egész szám, amely n- nél kisebb , akkor az n-edikre emelt d egybeesik d modulo n-vel .

Ha két számnak ugyanaz a maradéka, ha n-vel osztjuk, akkor azt mondjuk, hogy ezek egybevágó modulo n értékkel rendelkeznek . d modulo n egyszerűen egy d szám fennmaradó része, ha elosztjuk n-vel .

Például a 34 egyezik a 16-val (modulo 3)

34 modulo 3 = 1 és 16 modulo 3 = 1.

Fermat teszt az elsődlegességre

  1. Adott n számhoz válasszon véletlenszerű pozitív d számot úgy, hogy d < ; n.
  2. Számítsa ki a (d ^ n) modulo n értéket .
  3. d modulo n mindig lesz d ahogy mindig vegye d , amely kielégíti a feltételt d < ; n.
  4. Ha a (d ^ n) modulo n eredménye nem egyenlő d-vel , akkor d biztosan nem prím.
  5. Ha a (d ^ n) modulo n eredménye egyenlő d-vel , akkor jó az esély arra, hogy n prím.
  6. Válasszon ki egy másik véletlenszerű d-t, amely kielégíti a d < n feltételt, és ismételje meg a fenti lépéseket.

Megjegyzés : A bejegyzésben szereplő példák a Swift 4.1-et használják

Szükségünk van egy függvényre egy szám exponenciájának kiszámításához modulo másik szám.

Moduláris hatványozást használunk az értékek kiszámításához, ha a kitevő nagyobb, mint 1, mivel ez lehetővé teszi számítások elvégzését, miközben csak n- nél kisebb számokkal foglalkozunk ( modulo a fenti függvényben).

A Fermat-teszt véletlenszerűen választ egy d-t 1 és n-1 között ( a fenti függvényben az 1- et). A cél annak ellenőrzése, hogy a d n-edik teljesítményének maradék modulo n-e megegyezik-e d-vel.

A Fermat tesztet a megadott számláláshoz futtatjuk. Ha egy szám nem felel meg a Fermat-tesztnek, biztosak lehetünk benne, hogy ez nem elsődleges. Ha egy szám megfelel a Fermat-tesztnek, akkor nem garantált, hogy elsődleges. Megpróbáljuk csökkenteni az elsődleges teszt hibáinak valószínűségét azáltal, hogy a tesztet elégszer lefuttatjuk.

Ha egyre több d értéket próbálunk ki (véletlenszerű pozitív szám 1 és n-1 között), növelhetjük az eredménybe vetett bizalmunkat.