Primalitetstester
Test om et tal er et primtal og se præcis hvorfor: ægte prøvedivision op til √n for små og mellemstore tal, og en ægte Miller–Rabin-gennemgang for tal i kryptografisk størrelse.
🔒 Behandles helt i din browser - intet, du indtaster her, bliver nogensinde uploadet.
Resultat
Primalitetstesteren fortæller dig om et heltal er et primtal, og — i modsætning til de fleste online beregnere — viser den den faktiske algoritme der beviste det, ikke en cachet opslagstabel. Indtast et vilkårligt heltal, positivt eller negativt, lille eller enormt, og værktøjet afgør hvilken virkelig algoritme der skal køre baseret på dets størrelse.
For tal under 10¹² (en billion) kører det ægte prøvedivision: startende ved 2 afprøves hver heltalskandidat op til gulvet af √n som en mulig divisor, og standser i det øjeblik én går op (sammensat) eller bekræfter at ingen gør, når først hver kandidat op til √n er tjekket (primtal). Ved enorme kandidatantal begrænses det viste spor til de første ~18 afprøvede plus den sidste, med en ærlig bemærkning om hvor mange der blev sprunget over i visningen — men hver eneste kandidat tjekkes stadig af koden, ingen springes over i beregningen.
For tal på eller over denne grænse — det størrelsesområde der bruges i kryptografi — ville prøvedivision tage for lang tid, så værktøjet skifter til Miller–Rabin-primalitetstesten med et fast, deterministisk sæt af 13 primtalsvidner (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Præcis dette vidnesæt er et velkendt resultat: det har ingen falske positiver for noget n under 3.317.044.064.679.887.385.961.981 (cirka 3,3×10²⁴), en grænse fastlagt ved beregningsmæssig verifikation (se Sorenson & Webster, 2015, og den bredt reproducerede deterministiske vidnetabel det tilhører). Over denne grænse kører den samme test stadig, men værktøjet fortæller dig ærligt at garantien bliver en ekstremt stærk probabilistisk garanti snarere end en matematisk sikkerhed.
Miller–Rabin-sporet skriver n − 1 = 2ˢ × d med d ulige, gennemgår derefter ægte BigInt modulær eksponentiering — kvadrat-og-multiplikation, reducer modulo n ved hvert eneste trin så tallene aldrig eksploderer — bit for bit for det første vidne, og rapporterer hvert vidnes dom, inklusiv hvilket vidne der beviser sammensathed hvis tallet viser sig ikke at være et primtal. Alt kører lokalt i din browser: ingen server, ingen ekstern API, ingen data forlader din enhed.