Provjera primarnosti
Provjerite je li broj primaran i vidite točno zašto: stvarno probno dijeljenje do √n za male i srednje brojeve te autentični Miller–Rabinov postupak za brojeve kriptografske veličine.
🔒 U potpunosti se obrađuje u vašem pregledniku — ništa što ovdje unesete nikada se ne učitava.
Rezultat
Alat za provjeru primarnosti govori vam je li cijeli broj primaran i — za razliku od većine internetskih kalkulatora — pokazuje vam stvarni algoritam koji je to dokazao, a ne keširanu tablicu pretraživanja. Upišite bilo koji cijeli broj, pozitivan ili negativan, malen ili golem, a alat odlučuje koji će stvarni algoritam pokrenuti na temelju njegove veličine.
Za brojeve ispod 10¹² (jedan bilijun) pokreće stvarno probno dijeljenje: počevši od 2, isprobava svakog cjelobrojnog kandidata do najvećeg cijelog broja manjeg ili jednakog √n kao mogućeg djelitelja, zaustavljajući se u trenutku kada jedan od njih ravnomjerno dijeli (složen) ili potvrđujući da nijedan ne dijeli nakon što je svaki kandidat do √n provjeren (primaran). Za golem broj kandidata prikazani zapis ograničen je na prvih ~18 isprobanih plus posljednji, uz iskrenu napomenu o tome koliko ih je preskočeno u prikazu — no svaki pojedini kandidat i dalje je stvarno provjeren kodom, nijedan nije preskočen u izračunu.
Za brojeve na toj granici ili iznad nje — raspon veličina koji se koristi u kriptografiji — probno dijeljenje trajalo bi predugo, pa alat prelazi na Miller–Rabinov test primarnosti s fiksnim, determinističkim skupom od 13 prostih svjedoka (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Ovaj točan skup svjedoka dobro je poznat rezultat: nema lažno pozitivnih za nijedan n ispod 3.317.044.064.679.887.385.961.981 (oko 3,3×10²⁴), granice utvrđene računalnom provjerom (vidi Sorenson & Webster, 2015, i široko reproduciranu tablicu determinističkih svjedoka kojoj pripada). Iznad te granice isti se test i dalje izvodi, ali alat vam iskreno kaže da jamstvo postaje iznimno snažno probabilističko, a ne matematička sigurnost.
Miller–Rabinov zapis zapisuje n − 1 = 2ˢ × d s d neparnim, zatim prolazi kroz stvarno BigInt modularno potenciranje — kvadriraj-i-množi, reducirajući modulo n u svakom pojedinom koraku tako da brojevi nikada ne eksplodiraju — bit po bit za prvog svjedoka, i izvještava o presudi svakog svjedoka, uključujući koji svjedok dokazuje složenost ako se ispostavi da broj nije primaran. Sve se izvodi lokalno u vašem pregledniku: nema poslužitelja, nema vanjskog API-ja, nikakvi podaci nikada ne napuštaju vaš uređaj.