Primalitetssjekker

Primalitetskontrollen forteller deg om et heltall er primtall, og - i motsetning til de fleste kalkulatorer på nettet - viser deg den faktiske algoritmen som beviste det, ikke en bufret oppslagstabell. Skriv inn et hvilket som helst heltall, positivt eller negativt, lite eller enormt, og verktøyet bestemmer hvilken ekte algoritme som skal kjøres basert på størrelsen.

For tall under 10¹² (en billion), kjører den ekte prøvedivisjon: starter på 2 prøver den hver heltallskandidat opp til gulvet i √n som en mulig divisor, stopper øyeblikket en deler jevnt (sammensatt) eller bekrefter at ingen gjør det når hver kandidat opp til √n er sjekket (primtall). For store kandidattellinger er sporet som vises begrenset til den første ~18 forsøkte pluss den siste, med en ærlig merknad om hvor mange som ble hoppet over i displayet - men hver enkelt kandidat er fortsatt faktisk sjekket av koden, ingen blir hoppet over i beregningen.

For tall på eller over denne terskelen – størrelsesområdet som brukes i kryptografi – ville prøvedeling ta for lang tid, så verktøyet bytter til Miller-Rabin-primalitetstesten med et fast, deterministisk sett med 13 hovedvitner (2, 3, 5, 7, 11, 13, 17, 19, 23, 4, 19, 19, 23, 4, 19). Dette eksakte vitnesettet er et velkjent resultat: det har ingen falske positiver for noen n under 3,317,044,064,679,887,385,961,981 (omtrent 3,3×10²⁴), en grense etablert ved beregningsbekreftelse (se Sorenson & Webster, 2015-tabellen, som tilhører den utbredte gjengivelsen). Over den grensen kjører den samme testen fortsatt, men verktøyet forteller deg ærlig at garantien blir en ekstremt sterk sannsynlighet snarere enn en matematisk sikkerhet.

Miller–Rabin-sporet skriver n − 1 = 2ˢ × d med d odd, og går deretter gjennom reell BigInt-modulær eksponentiering - kvadrat-og-multipliker, reduserer modulo n ved hvert enkelt trinn slik at tallene aldri eksploderer - bit for bit for det første vitnet, og rapporterer hvert vitnes bevis om dommen er sammensatt, inkludert hvilket vitne som ikke er sammensatt. Alt kjører lokalt i nettleseren din: ingen server, ingen ekstern API, ingen data forlater enheten din.