Primality Checker

Primalitetskontrollen talar om för dig om ett heltal är primtal, och - till skillnad från de flesta miniräknare online - visar dig den faktiska algoritmen som bevisade det, inte en cachad uppslagstabell. Skriv valfritt heltal, positivt eller negativt, litet eller enormt, och verktyget bestämmer vilken riktig algoritm som ska köras baserat på dess storlek.

För tal under 10¹² (en biljon), kör den äkta provdelning: från och med 2, försöker den varje heltalskandidat upp till golvet i √n som en möjlig divisor, stoppar det ögonblick man delar jämnt (sammansatt) eller bekräftar att ingen gör det när alla kandidater upp till √n har markerats (primtal). För stora antal kandidater begränsas spåret som visas till den första ~18 försökte plus den sista, med en ärlig notering om hur många som hoppades över i displayen - men varje enskild kandidat kontrolleras fortfarande faktiskt av koden, ingen hoppas över i beräkningen.

För siffror på eller över den tröskeln - storleksintervallet som används i kryptografi - skulle provdelning ta för lång tid, så verktyget växlar till Miller–Rabins primatsteste med en fast, deterministisk uppsättning av 13 primära vittnen (2, 3, 5, 7, 11, 13, 17, 19, 23, 4, 19, 7, 19, 23, 13, 29). Denna exakta vittnesuppsättning är ett välkänt resultat: den har inga falska positiva resultat för något n under 3,317,044,064,679,887,385,961,981 (cirka 3,3×10²⁴), en gräns som fastställts genom beräkningsverifiering (se Sorenson & Webster, 2015 tillhör den breda tabell). Ovanför den gränsen körs samma test fortfarande, men verktyget säger ärligt att garantin blir en extremt stark sannolikhet snarare än en matematisk säkerhet.

Miller–Rabin-spåret skriver n − 1 = 2ˢ × d med d udda, går sedan igenom verklig BigInt modulär exponentiering — kvadrat-och-multiplicera, vilket minskar modulo n vid varje enskilt steg så att siffrorna aldrig exploderar — bit för bit för det första vittnet, och rapporterar varje vittnes vittnes utslag, inklusive vilket vittnes utslag som inte är sammansatt. Allt körs lokalt i din webbläsare: ingen server, inget externt API, ingen data lämnar din enhet.