Redigerer 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 å [[Primtallsfaktorisering|faktorisere]] tallet. Dette skillet ligger til grunn for [[krypteringsalgoritme]]r som [[RSA]].

==Enkle metoder==

Den enkleste metoden er [[trial division]], som innebærer å gjennomsøke alle helltal fra 2 til <math>\sqrt n</math> 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 algoritmer|probabilistiske]], hvilket innebærer at tall som avgjøres å være sammansatte garantert ikke er primtall, men at [[Sammensatt tall|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.<ref>Donald Knuth, ''The Art of Computer Programming'' vol 2, s. 395</ref>

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)<sup>−''k''</sup>, 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<sup>16</sup>, 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 [[tidskompleksitet]]en 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

:<math> O((\ln n)^{5+\epsilon})</math>

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.

==Referanser==
<references/>
{{Autoritetsdata}}

[[Kategori:Tallteori]]
[[Kategori:Algoritmer]]