Preverjevalnik prvotnosti
Preizkusite, ali je število praštevilo, in natančno ugotovite, zakaj: pravo poskusno deljenje do √n za majhna in srednja števila ter pristen Miller–Rabinov vodnik za števila v velikosti kriptografije.
Rezultat
Preverjevalnik primalnosti vam pove, ali je celo število praštevilo, in vam – za razliko od večine spletnih kalkulatorjev – pokaže dejanski algoritem, ki je to dokazal, ne predpomnjene iskalne tabele. Vnesite poljubno celo število, pozitivno ali negativno, majhno ali ogromno, in orodje se glede na svojo velikost odloči, kateri pravi algoritem naj zažene.
Za števila pod 10¹² (en bilijon) izvede pristno poskusno deljenje: začenši pri 2 preizkusi vsakega kandidata do dna √n kot možnega delitelja, pri čemer se ustavi v trenutku, ko eno enakomerno deli (sestavljeno) ali potrdi, da nobena ne deluje, ko je vsak kandidat do √n preverjen (pra). Pri velikem številu kandidatov je prikazano sledenje omejeno na prvih ~18 preizkušenih plus končno, z pošteno opombo o tem, koliko jih je bilo preskočenih na prikazu – vendar je vsak posamezen kandidat še vedno dejansko preverjen s kodo, nobeden ni preskočen v izračunu.
Za števila na ali nad tem pragom – obseg velikosti, ki se uporablja v kriptografiji – bi poskusna delitev trajala predolgo, zato orodje preklopi na Miller–Rabinov test primarilnosti s fiksnim, determinističnim nizom 13 glavnih prič (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Ta natančen pričevalni niz 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²4), mejo, določeno z računskim preverjanjem (glej Sorenson & Webster, 2015 in široko reproducirano tabelo determinističnih prič). pripada). Nad to mejo se isti test še vedno izvaja, vendar vam orodje iskreno pove, da garancija postane izredno močna verjetnostna in ne matematična gotovost.
Miller–Rabinova sled zapiše n − 1 = 2ˢ × d z lihim d, nato se sprehodi skozi pravo modularno potenciranje BigInt – kvadriranje in množenje, zmanjševanje modula n na vsakem posameznem koraku, tako da števila nikoli ne eksplodirajo – po bitih za prvo pričo, in poroča o sodbi vsake priče, vključno s tem, katera priča dokaže sestavljenost, če se izkaže, da število ni pra. Vse deluje lokalno v vašem brskalniku: noben strežnik, noben zunanji API, nobeni podatki ne zapustijo vaše naprave.
Vaše datoteke in vnosi nikoli ne zapustijo te naprave. Obdelava poteka popolnoma brez povezave. 100 % varno.
Sprejeti formati in pravila
- Preizkusna sled deljenja: kandidati od 2 do √n, z deliteljem, ki dokazuje sestavljenost, ali poštenim dokazom primalite '√n preverjeno, delitelja ni bilo mogoče najti'.
- Deterministični Miller–Rabin s prvimi 13 glavnimi pričami (2 do 41) — dokazano pravilen pod 3.317.044.064.679.887.385.961.981 (≈3,3×10²⁴).
- Prava BigInt modularna stopenjska sled s kvadratom in množenjem, po bitih, tako da lahko vidite, da se a(^d) mod n dejansko izračuna.
Ključne prednosti
Primeri uporabe
- • Preverite primalnost števila za diskretno matematiko ali domačo nalogo CS, medtem ko vidite dejansko poskusno deljenje ali Miller–Rabinove korake, ne le odgovora da/ne.
- • Preverite pravilnost velikega praštevila kandidata, medtem ko se učite, kako se RSA in drugi kriptosistemi zanašajo na resnični Miller–Rabinov algoritem, pri čemer se modularno potenciranje sledi po delih.
- • Hitro potrdite, ali je določeno število, ki se nenehno pojavlja v uganki ali nizu problemov, praštevilo, preden nad to predpostavko zgradite nadaljnjo logiko.
Ocenite to orodje
