Primality Checker

Primalitetskontrollen fortæller dig, om et heltal er primtal, og - i modsætning til de fleste lommeregnere online - viser dig den faktiske algoritme, der beviste det, ikke en cachelagret opslagstabel. Indtast et hvilket som helst heltal, positivt eller negativt, lille eller enormt, og værktøjet beslutter, hvilken reel algoritme der skal køres baseret på dens størrelse.

For tal under 10¹² (en trillion) kører den ægte prøvedivision: Startende ved 2 prøver den hver heltalskandidat op til gulvet i √n som en mulig divisor, stopper det øjeblik, man deler ligeligt (sammensat) eller bekræfter, at ingen gør det, når hver kandidat op til √n er blevet markeret (primtal). For et stort antal kandidater er det viste spor begrænset til den første ~18 forsøgte plus den sidste, med en ærlig note om, hvor mange der blev sprunget over i displayet - men hver enkelt kandidat er stadig faktisk kontrolleret af koden, ingen springes over i beregningen.

For tal på eller over denne tærskel - størrelsesområdet brugt i kryptografi - ville prøveopdeling tage for lang tid, så værktøjet skifter til Miller-Rabin primatitetstesten med et fast, deterministisk sæt af 13 primære vidner (2, 3, 5, 7, 11, 13, 17, 19, 23, 4, 13, 7, 29). Dette nøjagtige vidnesæt er et velkendt resultat: det har ingen falske positiver for nogen n under 3.317.044.064.679.887.385.961.981 (ca. 3,3×10²⁴), en grænse etableret ved beregningsmæssig verifikation (se Sorenson & Webster, 2015, der tilhører den brede-reproducerede tabel). Over den grænse kører den samme test stadig, men værktøjet fortæller dig ærligt, at garantien bliver en ekstrem stærk sandsynlighed snarere end en matematisk sikkerhed.

Miller-Rabin-sporet skriver n − 1 = 2ˢ × d med ulige, og går derefter gennem reel BigInt-modulær eksponentiering - firkantet-og-multiplikér, reducerer modulo n ved hvert enkelt trin, så tallene aldrig eksploderer - bit for bit for det første vidne, og rapporterer hvert vidnes bedømmelse, hvis det ikke er vidnesbyrd, hvis det er sammensat. Alt kører lokalt i din browser: ingen server, ingen ekstern API, ingen data forlader nogensinde din enhed.