Priemchecker

De priemchecker vertelt u of een geheel getal priem is, en — in tegenstelling tot de meeste online calculators — laat hij u het daadwerkelijke algoritme zien dat het bewees, niet een gecachte opzoektabel. Voer een willekeurig geheel getal in, positief of negatief, klein of enorm, en de tool kiest op basis van de grootte welk echt algoritme hij uitvoert.

Voor getallen onder 10¹² (één biljoen) voert hij echte proefdeling uit: te beginnen bij 2 probeert hij elke gehele kandidaat tot en met het grootste gehele getal ≤ √n als mogelijke deler, en stopt zodra er een gelijkmatig deelt (samengesteld), of bevestigt dat er geen is nadat elke kandidaat tot √n is gecontroleerd (priem). Bij enorm veel kandidaten wordt het spoor beperkt tot de eerste ~18 geteste plus de laatste, met een eerlijke opmerking over hoeveel er in de weergave zijn overgeslagen — maar elke kandidaat wordt door de code nog steeds echt gecontroleerd, in de berekening wordt er geen overgeslagen.

Voor getallen op of boven die drempel — het groottebereik dat in cryptografie wordt gebruikt — zou proefdeling te lang duren, dus schakelt de tool over naar de Miller–Rabin-priemtest met een vaste, deterministische set van 13 priemgetuigen (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Deze exacte getuigenset is een bekend resultaat: hij heeft geen valse positieven voor enige n onder 3.317.044.064.679.887.385.961.981 (ongeveer 3,3×10²⁴), een grens die door computationele verificatie is vastgesteld (zie Sorenson & Webster, 2015, en de wijdverbreid gereproduceerde deterministische-getuigetabel waar hij bij hoort). Boven die grens draait dezelfde test nog steeds, maar de tool vertelt u eerlijk dat de garantie een extreem sterke probabilistische wordt in plaats van een wiskundige zekerheid.

Het Miller–Rabin-spoor schrijft n − 1 = 2ˢ × d met d oneven, doorloopt vervolgens de echte BigInt modulaire machtsverheffing — vierkantsvermenigvuldiging, waarbij bij elke stap modulo n wordt gereduceerd zodat de getallen nooit exploderen — bit voor bit voor de eerste getuige, en rapporteert het oordeel van elke getuige, inclusief welke getuige de samengesteldheid bewijst als het getal niet priem blijkt te zijn. Alles draait lokaal in uw browser: geen server, geen externe API, er verlaat nooit data uw apparaat.