Algarvulisuse kontrollija
Testi, kas arv on algarv, ja näe täpselt, miks: väikeste ja keskmiste arvude korral ehtne proovijagamine kuni √n-ni, krüptosuuruses arvude puhul tõeline Milleri-Rabini samm-sammuline lahenduskäik.
🔒 Töödeldud täielikult teie brauseris – midagi, mida siia sisestate, ei laadita kunagi üles.
Tulemus
Algarvulisuse kontrollija ütleb sulle, kas täisarv on algarv, ja erinevalt enamikust veebikalkulaatoritest näitab algoritmi, mis seda tõestas – mitte puhverdatud otsingutabelit. Trüki sisse ükskõik milline täisarv – positiivne või negatiivne, väike või hiiglaslik – ja tööriist valib selle suuruse põhjal sobiva algoritmi.
Arvude puhul, mis jäävad alla 10¹² (üks triljon), kasutab see ehtsat proovijagamist: alustades 2-st, proovib iga täisarvulist kandidaati kuni √n täisosani kui võimalikku jagajat, peatudes kohe, kui mõni jagab arvu täpselt (liitarvulisus), või tuvastab, et ükski ei jaga, kui kõik kandidaadid kuni √n-ni on läbi proovitud (algarvulisus). Väga paljude kandidaatide korral kuvatakse jäljes ainult umbes 18 esimest proovitud jagajat ja viimane, koos ausa märkega selle kohta, mitu vahele jäi – kuid kood kontrollib ikkagi tegelikult iga kandidaati, ühtegi ei jäeta arvutuses vahele.
Arvude puhul, mis on sellest lävest suuremad – see on krüptograafias kasutatav suurusvahemik – võtaks proovijagamine liiga kaua aega, nii et tööriist läheb üle Milleri-Rabini algarvulisuse testile, kasutades kindlat, deterministlikku 13 algarvust tunnistaja komplekti (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). See täpne tunnistajate komplekt on tuntud tulemus: sellel ei ole valepositiivseid tulemusi ühegi n korral, mis on väiksem kui 3 317 044 064 679 887 385 961 981 (umbes 3,3×10²⁴) – piir, mis on paika pandud arvutusliku verifitseerimisega (vt Sorenson & Webster, 2015, ja laialt levinud deterministlike tunnistajate tabel, kuhu see kuulub). Üle selle piiri test siiski töötab, kuid tööriist ütleb sulle ausalt, et garantii muutub ülitugevaks tõenäosuslikuks, mitte matemaatiliseks kindluseks.
Milleri-Rabini jälg kirjutab n − 1 = 2ˢ × d, kus d on paaritu, seejärel käib läbi tõelise BigInt modulaarse astendamise – ruutu tõstmine ja korrutamine, iga sammu järel mooduli n järgi taandamine, nii et arvud kunagi plahvatuslikult ei kasva – biti haaval esimese tunnistaja jaoks, ning annab teada iga tunnistaja otsuse, sealhulgas selle, milline tunnistaja tõestab liitarvulisuse, kui arv ei osutu algarvuks. Kõik toimub kohalikult sinu brauseris: ei ühtegi serverit, välist API-t ega andmeid, mis sinu seadmest lahkuksid.