Pirmumo tikrintuvas

Pirmumo tikrintuvas nurodo, ar sveikasis skaičius yra pirminis, ir, skirtingai nei dauguma internetinių skaičiuotuvų, rodo tikrąjį algoritmą, kuris tai įrodė, o ne talpykloje saugomą paieškos lentelę. Įveskite bet kokį sveikąjį skaičių, teigiamą ar neigiamą, mažą arba didžiulį, ir įrankis nusprendžia, kurį realų algoritmą vykdyti pagal jo dydį.

Skaičiams, mažesniems nei 10¹² (vienas trilijonas), jis atlieka tikrą bandomąjį padalijimą: pradedant nuo 2, jis bando kiekvieną sveikąjį skaičių iki √n žemiausio lygio kaip galimą daliklį, sustabdydamas momentą, kai vienas dalijasi tolygiai (sudėtinis) arba patvirtindamas, kad niekas nepadalija, kai yra patikrintas kiekvienas kandidatas iki √n (pirminis). Esant dideliam kandidatų skaičiui, rodomas pėdsakas yra apribotas iki pirmųjų ~18 bandymų ir paskutinio, sąžiningai pažymint, kiek jų buvo praleista ekrane, tačiau kiekvienas kandidatas vis tiek iš tikrųjų tikrinamas pagal kodą, skaičiuojant nė vienas nepraleidžiamas.

Skaičiams, atitinkantiems arba viršijančius tą slenkstį (dydžių diapazoną, naudojamą kriptografijoje), bandomasis padalijimas užtruktų per ilgai, todėl įrankis persijungia į Miller-Rabin pirmumo testą su fiksuotu deterministiniu 13 pagrindinių liudininkų rinkiniu (2, 3, 5, 7, 11, 13, 17, 19, 2, 3, 4, 1, 3, 3). Šis tikslus liudininkų rinkinys yra gerai žinomas rezultatas: jis neturi klaidingų teigiamų rezultatų, jei n yra mažesnis nei 3 317 044 064 679 887 385 961 981 (apie 3,3 × 10²⁴), ribą, nustatytą skaičiavimo patikrinimu (žr. priklauso). Virš šios ribos vis dar vykdomas tas pats testas, tačiau įrankis jums nuoširdžiai sako, kad garantija tampa ypač stipri tikimybe, o ne matematiniu tikrumu.

Millero-Rabino pėdsakas įrašo n − 1 = 2ˢ × d su d nelyginiu, tada pereina tikrąjį BigInt modulinį eksponentą – kvadratu ir daugyba, mažindamas modulo n kiekviename žingsnyje, kad skaičiai niekada nesprogtų – po truputį pirmajam liudininkui, ir praneša kiekvieno liudytojo sudėtinį verdiktą, jei liudytojas nepasitvirtins, įskaitant skaičių, kuris pasitvirtins. Viskas veikia lokaliai jūsų naršyklėje: jokio serverio, jokios išorinės API, jokie duomenys niekada nepalieka jūsų įrenginio.