Primaliteitscontrole

De primaliteitscontrole vertelt u of een geheel getal een priemgetal is, en toont u – in tegenstelling tot de meeste online rekenmachines – het daadwerkelijke algoritme dat dit heeft bewezen, en niet een in de cache opgeslagen opzoektabel. Typ een geheel getal, positief of negatief, klein of enorm, en de tool beslist welk echte algoritme moet worden uitgevoerd op basis van de grootte ervan.

Voor getallen onder de 10¹² (één biljoen) voert het een echte proefdeling uit: beginnend bij 2 probeert het elke kandidaat met gehele getallen tot aan de vloer van √n als mogelijke deler, stopt op het moment dat er één gelijkmatig wordt verdeeld (samengesteld) of bevestigt dat geen enkele kandidaat dit doet zodra elke kandidaat tot √n is gecontroleerd (prime). Voor grote aantallen kandidaten wordt het getoonde spoor beperkt tot de eerste ~18 geprobeerd plus de laatste, met een eerlijke opmerking over hoeveel er op het scherm zijn overgeslagen - maar elke afzonderlijke kandidaat wordt nog steeds feitelijk gecontroleerd door de code, geen enkele wordt overgeslagen in de berekening.

Voor getallen op of boven die drempel – het groottebereik dat in cryptografie wordt gebruikt – zou de proefverdeling te lang duren, dus schakelt het hulpmiddel over op de Miller-Rabin-primaliteitstest met een vaste, deterministische set van 13 hoofdgetuigen (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Deze exacte getuigenset is een bekend resultaat: er zijn geen valse positieven voor n onder 3.317.044.064.679.887.385.961.981 (ongeveer 3,3×10²⁴), een grens die is vastgesteld door computationele verificatie (zie Sorenson & Webster, 2015, en de veelgebruikte deterministische getuigentabel waartoe deze behoort). Boven die grens loopt dezelfde test nog steeds, maar de tool vertelt je eerlijk dat de garantie een extreem sterke probabilistische garantie wordt in plaats van een wiskundige zekerheid.

Het Miller-Rabin-trace schrijft n - 1 = 2ˢ × d met d oneven, en doorloopt vervolgens de echte BigInt modulaire machtsverheffing - kwadrateren en vermenigvuldigen, waarbij modulo n bij elke stap wordt verminderd zodat de getallen nooit exploderen - beetje bij beetje voor de eerste getuige, en rapporteert het oordeel van elke getuige, inclusief welke getuige de samengesteldheid bewijst als het getal geen priemgetal blijkt te zijn. Alles draait lokaal in uw browser: geen server, geen externe API, geen enkele data verlaat ooit uw apparaat.