Primtalstest

Ett primtalstest är en algoritm som avgör huruvida ett givet heltal n är ett primtal, det vill säga inte delbart med något heltal förutom 1 och n självt. Att avgöra huruvida ett tal är primt är beräkningsmässigt betydligt enklare än att faktorisera det. Denna skillnad ligger till grund för krypteringsalgoritmer som exempelvis RSA.

Den enklaste algoritmen att testa om n är ett primtal är att försöka dela n med alla heltal från 2 till ${\displaystyle {\sqrt {n}}}$ för att se om det går jämnt upp. Om inget tal i detta intervall delar n, är n ett primtal. Metoden är med dagens datorer effektiv för tal upp till cirka 15 siffror, och kan även användas för att bevisa att större tal sammansatta (inte prima) genom att hitta små faktorer, men är obrukbar för att bevisa att stora tal är prima.

De snabbaste primtalstesten för stora tal är sannolikhetsbaserade. Testen går ut på att sammansatta tal sållas bort, tal som de klassar som sammansatta är garanterat inte primtal men sammansatta tal kan felaktigt utpekas som prima. Sådana metoder duger inte för att matematiskt bevisa att tal är prima, men är fullt tillräckliga för nästan alla praktiska tillämpningar eftersom sannolikheten för felaktiga svar kan göras astronomiskt låg, exempelvis lägre än sannolikheten för att beräkningens utgång skulle ha påverkats av kosmisk strålning som stört kretsarna i datorn.^[1]

Det enklaste och snabbaste probabilistiska primtalstestet är Fermats primtalstest. Man väljer ett heltal a som är relativt primt till n och beräknar a^{n − 1} modulo n.Om svaret inte är 1, så är n sammansatt. Om svaret är 1, så kan n vara ett primtal.

Detta ger dessvärre fel svar tämligen ofta och därmed måste det kompletteras med någon mer robust metod. Standardtestet är idag Miller-Rabins test, exempelvis använt av många datoralgebrasystem, vars tillförlitlighet kan justeras till godtycklig nivå genom att välja rätt uppsättning primtal som "vittnen" för att n är ett primtal. Om k stycken små primtal väljs som vittnen, är sannolikheten för att Miller-Rabin-testet tar fel högst (1/4)^k, och troligtvis mycket mindre i praktiken. Genom att välja specifika, välstuderade uppsättningar tal kan Miller-Rabin-testet göras fullständigt säkert för all tal mindre än 10¹⁶, och är då mycket snabbare än trial division. Miller-Rabins test är en förbättring av Solovay-Strassens test.

Deterministiska test kan rigoröst bevisa att ett tal är primt, men är i regel långsammare än probabilistiska metoder. Det mest använda deterministiska testet är ECPP som använder elliptiska kurvor. Metoden ger inte bara svaret primt/sammansatt utan returnerar även ett formellt bevis vars riktighet kan verifieras utan att upprepa hela beräkningen.

Den optimala tidskomplexiteten för primtalstest är ett välstuderat teoretiskt problem. Upptäckten av AKS-algoritmen år 2002 innebär att deterministiska primtalsbevis bevisligen är möjliga i polynomiell tid. ECPP har även sedan tidigare förmodats ha tidskomplexiteten

${\displaystyle O((\ln n)^{5+\epsilon })}$

vilket är en polynomiell tid, men detta har liksom för flera andra primtalstest ännu inte bevisats rigoröst.

För tal på speciella former är det ibland möjligt att genomföra deterministiska primtalstest betydligt snabbare än för tal i allmänhet. Detta gäller framför allt tal n för vilka n−1 eller n+1 har en enkel faktorisering. Det främsta exemplet är Mersennetal, tal som är ett mindre än en tvåpotens, för vilka Lucas-Lehmers test kan användas. Lucas-Lehmers test har använts för att hitta de största kända primtalen, som har över 9 miljoner siffror.