Kontrola primality

Kontrola primality vám povie, či je celé číslo prvočíslo, a na rozdiel od väčšiny online kalkulačiek vám ukáže skutočný algoritmus, ktorý to dokázal, nie vyhľadávaciu tabuľku uloženú vo vyrovnávacej pamäti. Zadajte akékoľvek celé číslo, kladné alebo záporné, malé alebo obrovské, a nástroj rozhodne, ktorý skutočný algoritmus sa má spustiť na základe jeho veľkosti.

Pre čísla menšie ako 10¹² (jeden bilión) spustí skutočné skúšobné delenie: počnúc od 2 skúša každého kandidáta na celé číslo až po dno √n ako možného deliteľa, zastaví sa v momente, keď sa delí rovnomerne (zložené), alebo sa nepotvrdí, že po skontrolovaní každého kandidáta do √n (prvočíslo) žiadne nedelí. Pri veľkom počte kandidátov je zobrazená stopa obmedzená na prvých ~18 vyskúšaných plus posledný, s úprimnou poznámkou o tom, koľko bolo na displeji preskočených – ale každý jeden kandidát je stále skutočne kontrolovaný kódom, žiadny nie je pri výpočte preskočený.

Pre čísla na tomto prahu alebo nad ním – rozsah veľkostí používaný v kryptografii – by skúšobné delenie trvalo príliš dlho, takže nástroj sa prepne na Miller-Rabinov test primality s pevnou, deterministickou sadou 13 hlavných svedkov (2, 3, 5, 7, 11, 13, 17, 19, 23, 237, 31, 11, ). Tento presný súbor svedkov je dobre známy výsledok: nemá žiadne falošné pozitíva pre žiadne n nižšie ako 3 317 044 064 679 887 385 961 981 (približne 3,3 × 10²⁴), hranicu stanovenú výpočtovou verifikáciou (pozri Sorenson & Webster, tabuľka reprodukovateľnosti a determinovanosti z roku 2015). Nad touto hranicou stále prebieha rovnaký test, ale nástroj vám úprimne povie, že záruka sa stáva extrémne silnou pravdepodobnostnou, a nie matematickou istotou.

Miller-Rabinova stopa zapíše n − 1 = 2ˢ × d s d nepárne, potom prejde skutočným modulárnym umocňovaním BigInt – štvorcom a násobením, čím sa znižuje modulo n v každom jednotlivom kroku, takže čísla nikdy nevybuchnú – kúsok po kúsku pre prvého svedka, a ohlási verdikt každého svedka, vrátane toho, ktoré číslo sa ukáže ako zložené. Všetko beží lokálne vo vašom prehliadači: žiadny server, žiadne externé API, žiadne dáta nikdy neopustia vaše zariadenie.