Preizkuševalnik praštevilskosti
Preizkusite, ali je število praštevilo, in natančno poglejte, zakaj: pravo deljenje s poskušanjem do √n za manjša in srednje velika števila ter pristen prikaz Miller–Rabinovega testa za kriptografsko velika števila.
🔒 V celoti obdelano v vašem brskalniku – nič, kar tukaj vnesete, ni nikoli naloženo.
Rezultat
Preizkuševalnik praštevilskosti vam pove, ali je celo število praštevilo, in – za razliko od večine spletnih kalkulatorjev – pokaže dejanski algoritem, ki je to dokazal, ne pa vnaprej pripravljene tabele. Vnesite poljubno celo število, pozitivno ali negativno, majhno ali ogromno, orodje pa se glede na njegovo velikost samo odloči, kateri pravi algoritem bo uporabilo.
Za števila pod 10¹² (en bilijon) izvede pravo deljenje s poskušanjem: začne pri 2 in preizkusi vsak celoštevilski kandidat do celega dela √n kot morebitni delitelj; ustavi se, takoj ko kak kandidat deli število brez ostanka (sestavljeno), ali pa potrdi praštevilskost, ko preveri vse kandidate do √n in nobeden ne deli brez ostanka (praštevilo). Pri zelo velikem številu kandidatov je prikazana sled omejena na prvih približno 18 preizkušenih in zadnjega, z iskrenim pojasnilom, koliko jih je bilo v prikazu izpuščenih – vendar je vsak kandidat v kodi dejansko preverjen, nobeden ni izpuščen pri izračunu.
Za števila, ki dosegajo ali presegajo ta prag – torej velikostni razred, ki se uporablja v kriptografiji – bi deljenje s poskušanjem trajalo predolgo, zato orodje preklopi na Miller–Rabinov test praštevilskosti s fiksnim, determinističnim naborom 13 praštevilskih prič (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Ta natančen nabor prič je dobro znan rezultat: nima lažno pozitivnih rezultatov za noben n pod 3.317.044.064.679.887.385.961.981 (približno 3,3×10²⁴), kar je meja, potrjena z računskim preverjanjem (glej Sorenson & Webster, 2015, in razširjeno razpredelnico determinističnih prič, katere del je). Nad to mejo se isti test še vedno izvede, vendar vam orodje iskreno pove, da jamstvo postane izjemno močno verjetnostno in ne več matematična gotovost.
Sled Miller–Rabinovega testa zapiše n − 1 = 2ˢ × d z lihim d, nato pa korak za korakom, bit za bitom, izvede pravo modularno potenciranje BigInt – po metodi kvadriraj-in-množi, z redukcijo po modulu n pri vsakem koraku, tako da števila nikoli ne eksplodirajo – za prvo pričo ter poroča o razsodbi vsake priče, vključno s tem, katera priča dokaže sestavljenost, če se izkaže, da število ni praštevilo. Vse teče lokalno v vašem brskalniku: brez strežnika, brez zunanjega API-ja, noben podatek nikoli ne zapusti vaše naprave.