Primaality Checker

Primaalisuuden tarkistus kertoo, onko kokonaisluku alkuluku, ja - toisin kuin useimmat online-laskimet - näyttää todellisen algoritmin, joka todisti sen, ei välimuistissa olevan hakutaulukon. Kirjoita mikä tahansa kokonaisluku, positiivinen tai negatiivinen, pieni tai valtava, ja työkalu päättää, mikä todellinen algoritmi suoritetaan sen koon perusteella.

Alle 10¹²:n (yksi biljoona) luvuille se suorittaa aidon koejaon: alkaen luvusta 2, se kokeilee jokaista kokonaislukuehdokasta √n:n lattiaan saakka mahdollisena jakajana, pysäyttäen hetken, jolloin yksi jakaantuu tasaisesti (yhdistetty) tai vahvistaa, että yksikään ei tee sitä, kun jokainen ehdokas √n:ään asti on tarkistettu (alkuluku). Suurissa ehdokasmäärissä näytettävä jälki rajataan ensimmäiseen ~18 kokeiltuun ja viimeiseen, ja siinä on rehellinen huomautus siitä, kuinka monta ohitettiin näytössä – mutta jokainen yksittäinen ehdokas tarkistetaan silti koodilla, eikä yhtäkään ei ohiteta laskennassa.

Kyseisen kynnyksen tai sen yläpuolella olevien lukujen – kryptografiassa käytetyn kokoalueen – koejako kestäisi liian kauan, joten työkalu siirtyy Miller–Rabinin primaalisuustestiin kiinteällä, deterministisellä 13:n päätodistajan joukolla (2, 3, 5, 7, 11, 13, 17, 19, 2, 3, 3). Tämä tarkka todistajajoukko on hyvin tunnettu tulos: sillä ei ole vääriä positiivisia tuloksia millekään n:lle, joka on alle 3 317 044 064 679 887 385 961 981 (noin 3,3 × 10²⁴), joka on laskennallisen verifioinnin avulla määritetty raja (katso Sorenson & Webster, uudelleentarkastettu ja determinoitu taulukko 20. kuuluu). Tämän rajan yläpuolella sama testi toimii edelleen, mutta työkalu kertoo rehellisesti, että takuusta tulee erittäin vahva todennäköisyys, ei matemaattinen varmuus.

Miller–Rabin-jäljittää n − 1 = 2ˢ × d d odd:lla, sitten käy läpi todellisen BigInt-modulaarisen eksponentioarvon – neliö ja kerro, pienentäen modulo n:tä jokaisessa vaiheessa, jotta luvut eivät koskaan räjähtäisi – pala kerrallaan ensimmäiselle todistajalle, ja raportoi jokaisen todistajan tuomion, jos todistaja ei osoittautuisi, mukaan lukien kumpi todistaja ei ole. Kaikki toimii paikallisesti selaimessasi: ei palvelinta, ei ulkoista APIa, mitään tietoja ei koskaan poistu laitteestasi.