Redigerer Primtallstest (avsnitt)

==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]].