Elsődlegesség-ellenőrző

Az elsődlegesség-ellenőrző megmondja, hogy egy egész szám prímszám-e, és – a legtöbb online számológéptől eltérően – a tényleges algoritmust mutatja, amely ezt bizonyította, nem pedig egy gyorsítótárazott keresési táblázatot. Írjon be tetszőleges egész számot, legyen az pozitív vagy negatív, kicsi vagy hatalmas, és az eszköz a mérete alapján eldönti, hogy melyik valós algoritmust futtassa.

A 10¹² (egy billió) alatti számok esetében valódi próbaosztást hajt végre: 2-től kezdve minden jelölt egész számot megpróbál √n aljáig lehetséges osztóként, megállítja azt a pillanatot, amikor az egyik egyenletesen osztódik (összetett), vagy megerősíti, hogy egyik sem osztja, ha minden √n-ig terjedő jelöltet ellenőriztek (prím). Hatalmas jelöltszámok esetén a megjelenített nyom az első ~18 kipróbálásra és az utolsóra korlátozódik, és őszintén megjegyzi, hogy hányat hagytak ki a kijelzőn – de a kód még mindig minden egyes jelöltet ellenőriz, a számítás során egyik sem kerül kihagyásra.

A küszöbértéket elérő vagy azt meghaladó számok esetében – a kriptográfiában használt mérettartományban – a próbaosztás túl sokáig tartana, ezért az eszköz átvált a Miller–Rabin primalitástesztre egy fix, determinisztikus, 13 elsődleges tanúból álló halmazzal (2, 3, 5, 7, 11, 13, 17, 19, 9, 3, 3). Ez a pontos tanúkészlet egy jól ismert eredmény: nincs hamis pozitív pozitívuma egyetlen n-re sem 3 317 044 064 679 887 385 961 981 (kb. 3,3 × 10²⁴) alatti értékre, amely korlátot számítási ellenőrzéssel állapítottak meg (lásd Sorenson & Webster, a széleskörűen determinált táblázat tartozik). Ezen túlmenően ugyanaz a teszt fut le, de az eszköz őszintén megmondja, hogy a garancia inkább egy rendkívül erős valószínűségi, mintsem matematikai bizonyossággá válik.

A Miller–Rabin nyomkövetés n − 1 = 2ˢ × d-t ír d páratlan értékkel, majd a valós BigInt moduláris hatványozáson megy keresztül – négyzet és szorzás, csökkentve a modulo n-t minden egyes lépésben, hogy a számok soha ne robbanjanak fel – apránként az első tanú esetében, és minden tanú összetételét jelenti, ha a tanú nem bizonyul, beleértve azt is, hogy melyik tanúnak bizonyul. Minden helyileg fut a böngészőben: nincs szerver, nincs külső API, és semmilyen adat nem hagyja el az eszközt.