primalitetstest

Et primalitetstest er en beregningsmetode for å avgjøre om et helt tall n er et primtall eller ikke. Primalitetstesting spiller en sentral rolle i kryptografi og matematisk forskning, der det ofte kreves store primtall eller svært beviste primtall.

Metoder for primalitet varierer i sikkerhet og effektivitet. Enkle metoder inkluderer prøving av divisorer opp til kvadratroten av n, som fungerer for små tall men blir upraktiske for store tall på grunn av tidskompleksiteten omtrent O(sqrt(n)). For å finne mange primtall opp til et gitt tall brukes Sieve of Eratosthenes, som har effektiv tidskompleksitet omtrent O(N log log N) og O(N) minnebruk.

For enkeltstående tall brukes primtitetstester som Miller-Rabin og andre probabilistiske tester. Miller-Rabin tester om et tall sannsynligvis er et primtall; ved hver uavhengig iterasjon reduseres feilmarginen betydelig, og man kan stoppe etter et forhåndsbestemt antall iterasjoner. Dette gir raske tester for svært store tall, med en kontrollert sannsynlighet for feil. Det finnes også deterministiske varianter av Miller-Rabin som gir sikker avgjørelse for tall innen visse størrelsesområder, og andre fullstendige tester som AKS primalitetstest, som teoretisk opererer i polynomielt tidsrom, men som i praksis ofte er mindre brukte på store tall på grunn av lavere praktisk ytelse.

Spesialiserte bevis og sertifikater, som elliptic curve primality proving (ECPP), kan generere bevis for at et tall er prime, noe som muliggjør uavhengig verifikasjon av primaliteten.

Bruksområder inkluderer primtallsgenerering for kryptografiske nøkler, pruebas i numerisk forskning og forståelse av tallteori.