Alkulukutesti
Testaa, onko luku alkuluku, ja näe tarkalleen miksi: aito jakokokeilu √n:ään asti pienille ja keskisuurille luvuille, ja todellinen Miller–Rabin-läpikäynti kryptografian kokoisille luvuille.
🔒 Käsitelty kokonaan selaimessasi – mitään tähän kirjoittamaasi ei koskaan ladata.
Tulos
Alkulukutesti kertoo, onko kokonaisluku alkuluku, ja toisin kuin useimmat verkon laskurit, se näyttää todellisen algoritmin, joka sen todisti, ei välimuistista haettua taulukkoa. Kirjoita mikä tahansa kokonaisluku, positiivinen tai negatiivinen, pieni tai valtava, ja työkalu valitsee koon perusteella, kumpaa aitoa algoritmia käytetään.
Alle 10¹²:n (biljoonan) luvuille se suorittaa aidon jakokokeilun: aloittaen 2:sta se kokeilee jokaista kokonaislukuehdokasta √n:n alaraja-arvoon asti mahdollisena jakajana, pysähtyen heti, kun yksi jakaa tasan (yhdistetty luku), tai varmistuen, ettei yhtään löydy, kun kaikki ehdokkaat √n:ään asti on tarkistettu (alkuluku). Erittäin monen ehdokkaan tapauksessa näytetty jälki rajataan noin 18 ensimmäiseen kokeiltuun plus viimeiseen, ja rehellinen huomautus kertoo, kuinka monta jätettiin näyttämättä — mutta koodi todella tarkistaa jokaisen ehdokkaan, eikä laskennassa ohiteta yhtään.
Tätä rajaa suuremmille luvuille — joita käytetään kryptografiassa — jakokokeilu veisi liian kauan, joten työkalu siirtyy Miller–Rabin-alkulukutestiin käyttäen kiinteää, determinististä 13 alkutodistajan joukkoa (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Tämä todistajajoukko on tunnettu tulos: se ei tuota vääriä positiivisia millekään alle 3 317 044 064 679 887 385 961 981 olevalle n:lle (noin 3,3×10²⁴), mikä on laskennallisesti varmennettu raja (ks. Sorenson & Webster, 2015, ja siihen kuuluva laajalti toistettu determinististen todistajien taulukko). Tämän rajan yläpuolella sama testi yhä suoritetaan, mutta työkalu kertoo rehellisesti, että takuu muuttuu matemaattisen varmuuden sijaan äärimmäisen vahvaksi todennäköisyydeksi.
Miller–Rabin-jälki kirjoittaa n − 1 = 2ˢ × d, jossa d on pariton, ja käy sitten läpi todellisen BigInt-modulaarieksponentin — neliöimällä ja kertomalla, pelkistäen modulo n:n jokaisessa vaiheessa, jotteivät luvut koskaan räjähdä — bitti bitiltä ensimmäiselle todistajalle, ja raportoi kunkin todistajan tuomion, mukaan lukien sen, mikä todistaja osoittaa yhdistetyksi, jos luku ei ole alkuluku. Kaikki tapahtuu paikallisesti selaimessasi: ei palvelinta, ei ulkoista APIa, data ei koskaan poistu laitteeltasi.