Primtallstest

En primtalstest er en algoritme som avgjør hvorvidt et gitt heltall n er et primtall, det vil si at det ikke er delbart med noe heltall foruten 1 og n (seg selv). Å avgjøre hvorvidt ett tall er et primtall er beregningsmessig betydelig enklere enn å faktorisere tallet. Dette skillet ligger til grunn for krypteringsalgoritmer som RSA.

Enkle metoder

Den enkleste metoden er trial division, som innebærer å gjennomsøke alle helltal fra 2 til ${\sqrt {n}}$ for å finne en faktor. Om ingen tall i dette intervallet deler n, er n ett primtall. Metoden er med dagens datamaskiner effektiv for tall opp til cirka 15 siffer, og kan også anvendes for å bevise at større sammansatte tall (ikke prim) gjennom å finne små faktorer, men ubrukbar for å vise at store tall er primtall.

Probabilistiske metoder

De raskeste primtallstestene for store tall er probabilistiske, hvilket innebærer at tall som avgjøres å være sammansatte garantert ikke er primtall, men at sammensatte tall kan feilaktig utpekes som primtall. Slike metoder er ikke passende for å bevise at tall er primtall, men er fullt ut brukbare for nesten alle praktiske tilnærminger ettersom sannsynligheten for feil er astronomisk lav. Eksempelvis lavere enn sannsynligheten for at beregningsresultatet skulle vært påvirket av kosmisk stråling som forstyrrer datamaskinens kretskort.

Den enkleste og raskeste probalistiske primtallstesten er Fermats primtalstest, som dessverre gir feil svar ganske ofte og dermed må komplementeres med en noe mer robust metode. Standardtesten i dag er Miller-Rabins test, eksempelvis anvendt av mange algebrasystem implementert i datamaskiner, som kan justeres til et akseptabelt nivå gjennom å velge rette primtallsvitner. Om k små primtall velges som vitne, er sannsynligheten for at Miller-Rabin-testen gir feil høyst (1/4)^−k, og antageligvis mye mindre i praksis. Gjennom å velge spesifikke, velstuderte oppsetninger av primtall kan Miller-Rabin-testen gjøres fullstendig sikker for alle tall mindre enn 10¹⁶, og er da mye raskere enn trial division. Miller-Rabins test er en forbedring av Solovay-Strassens test.

Deterministiske metoder

Deterministiske tester kan rigorøst bevise at ett tall er primt, men er som regel langsommere en probabilistiske metoder. Det mest anvendte deterministiske testen er ECPP som anvender elliptiske kurver. Metoden gir ikke bare svaret primt/sammensatt, men returnerer også formelt bevis uten at hele beregningen må ramses opp.

Den optimale tidskompleksiteten for primtallstest er ett velstudert teoretisk problem. Oppdagelsen av AKS-algoritmen i år 2002 innebar at deterministiske primtallsbevis beviselig er mulige i polynomiell tid. Man antar at ECPP har tidskompleksiteten

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

hvilket er en polynomiell tid, men dette har som for flere andre primtallstester ikke blitt bevist rigorøst.

Spesialtilfeller

For tall på spesielle former er det i blant mulig å gjennomføre deterministiske primtalstester betydelig raskere. Dette gjelder spesielt tall n for hvilket n−1 eller n+1 har en enkel faktorisering. Det fremste eksempelet er mersennetall, tall som er ett mindre enn en topotens, for hvilke Lucas-Lehmers test kan anvendes. Lucas-Lehmers test har blitt anvendt for å finne de største kjente primtall, som har over 9 millioner siffer.