Alkuluvut

Alkuluvut, eli prime numbers, ovat luonnollisia lukuja suuremmia kuin 1, joilla on vain kaksi positiivista jakajaa: 1 ja itsensä. Esimerkkejä ovat 2, 3, 5, 7 ja 11. Parillinen alkuluku 2 on pienin alkuluku ja ainoa parillinen alkuluku.

Jokainen luku suurempi kuin 1 voidaan esittää yksiselitteisesti alkulukujen tulona, jäsennys ei riipu järjestyksestä. Tätä kutsutaan perustavaa pääteoreemaa: lopullinen kertolasku on uniikki, kun huomioidaan alkulukujen kerrannaiset, esimerkiksi 60 = 2^2 × 3 × 5.

Alkuluvut erottuvat tilastollisesti: niiden määrä pienenee suhteessa n:n kasvuun, ja luonteenomaisena tuloksena on Priminen lukujen teoreema, joka sanoo pi(x) ~ x/log x, missä pi(x) on alkulukujen lukumäärä enintään x. Sieve of Eratosthenes on muinainen ja tehokas algoritmi löytää kaikki alkuluvut annettuun ylärajaan.

Käytännön sovelluksissa alkulukujen ominaisuudet ovat keskeisiä, erityisesti kryptografiassa. Suurten alkulukujen löytämiseen käytetään sekä deterministisiä että epävarmoja primitiviteetteja, kuten Miller–Rabin -testi, ja joskus AKS-primaliteettitestiä. Alkuluvut ovat myös tärkeä tutkimuskohde lukuteoriassa, esimerkiksi kaksoissijais- (twin prime) ja muita konjetihtejä koskevat kysymykset sekä todistukset niiden yleisyydestä.

Historian kannalta on huomattu, että alkulukujen lukumäärän kasvu on ääretön: Euclid osoitti ko. seikan jo muinaisessa Kreikassa. Alkulukujen tutkimus yhdistää teoreettisen kaavan, algoritmit ja käytännön sovellukset.