Primtallsjekker
Test om et tall er et primtall, og se nøyaktig hvorfor: ekte prøvedivisjon opp til √n for små og mellomstore tall, og en ekte Miller–Rabin-gjennomgang for tall i kryptografisk størrelse.
🔒 Behandles i sin helhet i nettleseren din – ingenting du skriver inn her blir noen gang lastet opp.
Resultat
Primtallsjekkeren forteller deg om et heltall er et primtall, og — i motsetning til de fleste kalkulatorer på nettet — viser den den faktiske algoritmen som beviste det, ikke en forhåndslaget oppslagstabell. Skriv inn et hvilket som helst heltall, positivt eller negativt, lite eller enormt, og verktøyet bestemmer hvilken ekte algoritme som skal brukes basert på størrelsen.
For tall under 10¹² (én billion) utfører det ekte prøvedivisjon: med start på 2 prøver det hver heltallskandidat opp til gulvet av √n som en mulig divisor. Det stopper i det øyeblikket en divisor går opp (sammensatt), eller bekrefter at ingen går opp når hver kandidat opp til √n er sjekket (primtall). For enorme antall kandidater viser sporingen bare de første ~18 som ble prøvd, pluss den siste, med en ærlig merknad om hvor mange som ble utelatt fra visningen — men hver eneste kandidat blir faktisk sjekket av koden, ingen hoppes over i beregningen.
For tall på eller over denne terskelen — størrelsesområdet som brukes i kryptografi — ville prøvedivisjon tatt for lang tid, så verktøyet bytter til Miller–Rabins primtallstest med et fast, deterministisk sett med 13 primtallsvitner (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Dette nøyaktige vitnesettet er et velkjent resultat: det har ingen falske positiver for noen n under 3 317 044 064 679 887 385 961 981 (ca. 3,3×10²⁴), en grense etablert ved beregningsverifisering (se Sorenson & Webster, 2015, og den mye gjengitte deterministiske vitnetabellen det tilhører). Over denne grensen kjører den samme testen fortsatt, men verktøyet forteller deg ærlig at garantien blir en ekstremt sterk probabilistisk garanti snarere enn en matematisk sikkerhet.
Miller–Rabin-sporingen skriver n − 1 = 2ˢ × d der d er odde, og går deretter gjennom ekte BigInt modulær eksponentiering — kvadrat-og-multipliser, med reduksjon modulo n ved hvert eneste trinn slik at tallene aldri vokser seg uhåndterlig store — bit for bit for det første vitnet, og rapporterer hvert vitnes vurdering, inkludert hvilket vitne som beviser at tallet er sammensatt hvis det viser seg at det ikke er et primtall. Alt kjøres lokalt i nettleseren din: ingen server, intet eksternt API, ingen data forlater noen gang enheten din.