Primtalskontroll
Testa om ett tal är ett primtal och se exakt varför: riktig trial division upp till √n för små och medelstora tal, och en genuin Miller–Rabin-genomgång för kryptografiskt stora tal.
🔒 Bearbetas helt i din webbläsare – ingenting du anger här laddas någonsin upp.
Resultat
Primtalskontrollen talar om ifall ett heltal är ett primtal, och – till skillnad från de flesta kalkylatorer på nätet – visar den den faktiska algoritmen som bevisade det, inte en cachad uppslagstabell. Skriv in ett heltal, positivt eller negativt, litet eller enormt, så avgör verktyget vilken riktig algoritm som ska köras baserat på talets storlek.
För tal under 10¹² (en biljon) körs genuin trial division: den börjar på 2, testar varje heltalskandidat upp till golv(√n) som en möjlig divisor, stannar så fort en jämnt delar (sammansatt) eller bekräftar att ingen gör det när varje kandidat upp till √n har kontrollerats (primtal). För enorma kandidatantal är spårningen som visas begränsad till de första ~18 försöken plus den sista, med en ärlig notering om hur många som hoppades över i visningen – men varje enskild kandidat kontrolleras fortfarande faktiskt av koden, ingen hoppas över i beräkningen.
För tal vid eller över den tröskeln – den storleksordning som används inom kryptografi – skulle trial division ta för lång tid, så verktyget växlar till Miller–Rabins primtalstest med en fast, deterministisk uppsättning av 13 primtalsvittnen (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Denna exakta vittnesuppsättning är ett välkänt resultat: den har inga falska positiva för något n under 3 317 044 064 679 887 385 961 981 (cirka 3,3×10²⁴), en gräns fastställd genom beräkningsverifiering (se Sorenson & Webster, 2015, och den vitt spridda deterministiska vittnestabell som den tillhör). Över den gränsen körs samma test fortfarande, men verktyget säger ärligt att garantin blir en extremt stark probabilistisk sådan snarare än en matematisk visshet.
Miller–Rabin-spårningen skriver n − 1 = 2ˢ × d med d udda, går sedan igenom äkta BigInt modulär exponentiering – square-and-multiply, reducera modulo n i varje enskilt steg så att talen aldrig exploderar – bit för bit för det första vittnet, och rapporterar varje vittnes utslag, inklusive vilket vittne som bevisar sammansatthet om talet visar sig inte vara ett primtal. Allt körs lokalt i din webbläsare: ingen server, inget externt API, ingen data lämnar någonsin din enhet.