Prímtesztelő

Ez a prímtesztelő megmondja, hogy egy egész szám prím-e, és – a legtöbb online számológéptől eltérően – megmutatja a tényleges algoritmust, amely bizonyította, nem egy gyorsítótárazott táblázatot. Adjon meg tetszőleges egész számot, pozitívat vagy negatívat, kicsit vagy hatalmasat, és az eszköz a mérete alapján dönti el, melyik valódi algoritmust futtatja.

10¹² (egybillió) alatti számoknál valódi próbaosztást végez: 2-től indulva minden egész jelöltet kipróbál √n alsó egészrészéig mint lehetséges osztót, és megáll, amint egy maradék nélkül oszt (összetett), vagy megerősíti, hogy egyik sem oszt, miután minden √n-ig lévő jelöltet ellenőrzött (prím). Nagyon sok jelölt esetén a megjelenített nyomon követés az első ~18 kipróbáltra és az utolsóra korlátozódik, egy becsületes megjegyzéssel arról, hányat hagyott ki a megjelenítés – de a kód valóban ellenőrzi mindegyik jelöltet, a számítás során egy sem marad ki.

E küszöbértéknél nagyobb vagy azzal egyenlő számoknál – a kriptográfiában használt mérettartomány – a próbaosztás túl sokáig tartana, ezért az eszköz a Miller–Rabin prímtesztre vált egy rögzített, determinisztikus, 13 prím tanúból álló halmazzal (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Ez a konkrét tanúhalmaz jól ismert eredmény: 3 317 044 064 679 887 385 961 981 (körülbelül 3,3×10²⁴) alatt nincs hamis pozitív eredménye, amely korlátot számításos ellenőrzéssel állapítottak meg (lásd Sorenson & Webster, 2015, és az ezt tartalmazó, széles körben reprodukált determinisztikus tanú táblázatot). E korlát felett a teszt továbbra is lefut, de az eszköz becsületesen közli, hogy a garancia matematikai bizonyosság helyett rendkívül erős valószínűségi garanciává válik.

A Miller–Rabin nyomon követés felírja n − 1 = 2ˢ × d alakot, ahol d páratlan, majd valódi BigInt moduláris hatványozáson lépked végig – négyzetre emelés és szorzás, minden egyes lépésnél modulo n redukálva, így a számok soha nem nőnek kezelhetetlenül – bitről bitre az első tanúnál, és minden tanú ítéletét közli, beleértve, hogy melyik tanú bizonyítja az összetettséget, ha a számról kiderül, hogy nem prím. Minden helyben, az Ön böngészőjében fut: nincs szerver, nincs külső API, semmilyen adat nem hagyja el az eszközét.