Provjera osnovnosti
Testirajte je li broj prost i provjerite točno zašto: pravo probno dijeljenje do √n za male i srednje brojeve i originalni Miller–Rabinov vodič za brojeve kriptografske veličine.
Rezultat
Provjera osnovnosti govori vam je li cijeli broj prost i - za razliku od većine online kalkulatora - pokazuje vam stvarni algoritam koji je to dokazao, a ne predmemoriranu tablicu pretraživanja. Upišite bilo koji cijeli broj, pozitivan ili negativan, malen ili ogroman, a alat odlučuje koji pravi algoritam pokrenuti na temelju svoje veličine.
Za brojeve ispod 10¹² (jedan trilijun), izvodi pravo probno dijeljenje: počevši od 2, isprobava svaki kandidat cijelog broja do dna √n kao mogućeg djelitelja, zaustavljajući se u trenutku kada se ravnomjerno dijeli (kompozitno) ili potvrđujući da nijedan ne radi kada je svaki kandidat do √n provjeren (prim). Za veliki broj kandidata, prikazano praćenje je ograničeno na prvih ~18 isprobanih plus konačni, uz iskrenu napomenu o tome koliko ih je preskočeno u prikazu — ali svaki pojedini kandidat još uvijek se stvarno provjerava kodom, niti jedan se ne preskače u izračunu.
Za brojeve na ili iznad tog praga — raspon veličine koji se koristi u kriptografiji — probno dijeljenje bi trajalo predugo, pa se alat prebacuje na Miller–Rabinov test primarnosti s fiksnim, determinističkim skupom od 13 primarnih 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žnih pozitivnih rezultata za bilo koji n ispod 3,317,044,064,679,887,385,961,981 (oko 3,3×10²⁴), granice utvrđene računskom verifikacijom (vidi Sorenson & Webster, 2015. i naširoko reproduciranu tablicu determinističkih svjedoka pripada). Iznad te granice i dalje se izvodi isti test, ali alat vam iskreno govori da jamstvo postaje iznimno jaka vjerojatnost, a ne matematička sigurnost.
Miller–Rabinov trag zapisuje n − 1 = 2ˢ × d s d neparnim, zatim prolazi kroz stvarno BigInt modularno potenciranje — kvadriranje i množenje, smanjenje modula n u svakom pojedinom koraku tako da brojevi nikada ne eksplodiraju — malo po malo za prvog svjedoka, i izvještava o presudi svakog svjedoka, uključujući i koji svjedok dokazuje složenost ako se ispostavi da broj nije prost. Sve radi lokalno u vašem pregledniku: nema poslužitelja, nema vanjskog API-ja, nikakvi podaci nikada ne napuštaju vaš uređaj.
Vaše datoteke i unosi nikada ne napuštaju ovaj uređaj. Obrada se odvija potpuno offline. 100% siguran.
Prihvaćeni formati i pravila
- Probni trag dijeljenja: kandidati od 2 do √n, s djeliteljem koji dokazuje složenost ili poštenim '√n provjerenim, nije pronađen djelitelj' dokazom primarnosti.
- Deterministički Miller–Rabin s prvih 13 glavnih svjedoka (2 do 41) — dokazano točnim ispod 3,317,044,064,679,887,385,961,981 (≈3,3×10²⁴).
- Pravi BigInt kvadratni i množeći modularni trag stepenovanja, malo po malo, tako da možete vidjeti da se a(^d) mod n zapravo izračunava.
Ključne prednosti
Slučajevi upotrebe
- • Provjerite primalnost broja za diskretnu matematičku ili CS domaću zadaću dok vidite stvarni pokušaj dijeljenja ili Miller–Rabinove korake, a ne samo odgovor da/ne.
- • Provjerite razumnost velikog prosta broja kandidata dok učite kako se RSA i drugi kriptosustavi oslanjaju na pravi Miller–Rabinov algoritam, s modularnim stepenovanjem koje se prati malo po malo.
- • Brzo potvrdite je li određeni broj koji se stalno pojavljuje u zagonetki ili skupu problema prost prije nego što na temelju te pretpostavke izgradite daljnju logiku.
Ocijenite ovaj alat
