Avainlukuja

Avainluvut eli alkulukut ovat luonnollisia lukuja suurempia kuin 1, joilla on täsmälleen kaksi positiivista jakajaa: 1 ja itsensä. Tämä tarkoittaa, ettei niillä ole muita jaollisuuksia. Esimerkkejä avainluvuista ovat 2, 3, 5, 7 ja 11. Luku 1 ei ole avainluku. Avainluvut ovat keskeisiä luvun teorian peruskiviä ja niitä esiintyy sekä teoreettisessa matematiikassa että käytännön sovelluksissa.

Peruslauseen mukaan jokainen suurempi kuin 1 oleva kokonaisluku on joko avainluku tai voidaan esittää yksikäsitteisesti avainlukujen tulona. Euclid osoitti avainlukujen äärettömyyden. Kaikki avainluvut suuremmat kuin 2 ovat parittomia; 2 on ainoa parillinen avainluku. Tiheydeltään alkulukujen määrä pienenee suuremmilla luvuilla, ja alle x olevien primien määrä on arviolta noin x/log x. Tämä jakautuminen on keskeinen osa lukuteoriaa.

Käytännön sovelluksissa avainluvut ovat keskeisiä kryptografiassa: suurilla avainluvuilla toteutettu salaus, kuten RSA, perustuu alkulukujen vaikeaan faktorointiin. Primaliteetin testaamiseen käytetään sekä epävarmoja että deterministisiä algoritmeja; tunnettuja esimerkkejä ovat Miller-Rabin-tyyppiset testit sekä AKS-primaliteetittaus. Tutkimuksessa on useita avoimia kysymyksiä, kuten twin primes -parien loputtomuus ja tarkemmat ennusteet primejen pitoisuudesta lyhyillä väleillä.