primtall

Primtall er positive heltall større enn én som kun har to positive divisorer: én og seg selv. Tall som 2, 3, 5, 7 og 11 er eksempler på primtall, mens sammensatte tall som 4, 6, 8 og 9 har flere faktorer. Det minste primtallet er 2, som også er det eneste even­tall som er primtall; alle andre primtall er oddetall.

Primtall spiller en sentral rolle i tallteori og har mange anvendelser innen kryptografi, spesielt i offentlige nøkkel­systemer som RSA, hvor sikkerheten hviler på vanskeligheten med å faktorisere store sammensatte tall i deres primfaktorer. Innen matematisk forskning er fordelingen av primtall et aktivt forskningsområde; den klassiske primtallsteoremet gir en asymptotisk beskrivelse av hvor ofte primtall forekommer, og sier at antallet primtall mindre enn en gitt verdi n er tilnærmet n / ln n.

Det finnes flere metoder for å teste om et tall er primtall. Den enkleste er prøvedeling med alle heltall opp til kvadratroten av tallet. Mer effektive algoritmer inkluderer Miller–Rabin-testen, en probabilistisk metode, og AKS-algoritmen, som er deterministisk og kjører i polynomisk tid. Siden 2 er det eneste evige primtallet, er det også den eneste primtallsfaktor som er et partall.

Primtall kan også kombineres til å danne spesielle tallsekvenser, som twin‑primes (par av primtall med differanse to) og Mersenne‑primtall, som har formen 2^p − 1 med p selv et primtall. Mange uløste problemer, som Twin Prime Conjecture og Goldbachs formodning, dreier seg om primtalls egenskaper og deres fordeling.