Pirminiškumo tikrintuvas
Patikrinkite, ar skaičius pirminis, ir aiškiai pamatykite, kodėl: realus daliklių perrinkimas iki √n mažiems ir vidutiniams skaičiams, ir tikras Millerio–Rabino testo žingsnių atvaizdavimas kriptografinio dydžio skaičiams.
🔒 Visiškai apdorojama jūsų naršyklėje – niekas, kurį čia įvedėte, niekada neįkeliama.
Rezultatas
Pirminiškumo tikrintuvas pasako, ar sveikasis skaičius yra pirminis, ir — skirtingai nei dauguma internetinių skaičiuotuvų — parodo tikrą jį įrodžiusį algoritmą, o ne iš anksto apskaičiuotą reikšmių lentelę. Įveskite bet kurį sveikąjį skaičių, teigiamą ar neigiamą, mažą ar milžinišką, ir įrankis pagal jo dydį nuspręs, kurį realų algoritmą taikyti.
Skaičiams iki 10¹² (vieno trilijono) vykdomas tikras daliklių perrinkimas: pradedant nuo 2, išbandomas kiekvienas sveikasis kandidatas iki √n sveikosios dalies kaip galimas daliklis, sustojant, kai tik vienas pasidalija be liekanos (sudėtinis), arba patvirtinant, kad nė vienas nepasidalijo, kai patikrinti visi kandidatai iki √n (pirminis). Milžiniškam kandidatų skaičiui rodoma pradžia (iki ~18 išbandytų) ir paskutinis, su sąžininga pastaba, kiek jų buvo praleista rodinyje — tačiau kiekvienas kandidatas realiai patikrinamas kodo, skaičiavimuose nepraleidžiamas nė vienas.
Skaičiams, pasiekusiems tą ribą ar už ją didesniems — dydžio, naudojamo kriptografijoje, — daliklių perrinkimas truktų per ilgai, todėl įrankis pereina prie Millerio–Rabino pirminiškumo testo su fiksuota, deterministine 13 pirminių liudytojų aibe (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Ši tiksli liudytojų aibė yra gerai žinomas rezultatas: ji neturi klaidingų teigiamų atsakymų jokiam n žemiau 3 317 044 064 679 887 385 961 981 (apie 3.3×10²⁴) — šią ribą nustatė skaičiuojamasis patikrinimas (žr. Sorenson & Webster, 2015, ir plačiai atkartojamą deterministinių liudytojų lentelę, kuriai ji priklauso). Už šios ribos tas pats testas vis dar vykdomas, tačiau įrankis sąžiningai praneša, kad garantija tampa ypač stipria tikimybine, o ne matematiniu tikrumu.
Millerio–Rabino eiga užrašo n − 1 = 2ˢ × d, kai d nelyginis, tada pereina realaus BigInt modulinio kėlimo žingsnius — daugybos-kvadratu metodą, redukuojant moduliu n kiekviename žingsnyje, kad skaičiai niekada neperaugtų, — bitas po bito pirmajam liudytojui, ir pateikia kiekvieno liudytojo verdiktą, įskaitant, kuris liudytojas įrodo sudėtingumą, jei paaiškėja, kad skaičius nėra pirminis. Viskas vyksta lokaliai jūsų naršyklėje: jokio serverio, jokio išorinio API, jokie duomenys niekada nepalieka jūsų įrenginio.