primaliteit

Primaliteit is de eigenschap van een natuurlijk getal groter dan 1 dat alleen deelbaar is door 1 en zichzelf. Getallen die aan deze eigenschap voldoen worden priemgetallen genoemd; getallen groter dan 1 die geen priem zijn, worden samengesteld genoemd. Het getal 1 is geen priem.

Priemgetallen dienen als bouwstenen van de gehele getallen. Volgens de stelling van de unieke factorisatie kan elk getal groter dan 1 uniek worden geschreven als een product van priemgetallen, met machten, en de volgorde doet er niet toe.

Primaliteit controleren kan met verschillende methodes. Een eenvoudige methode is deling door alle mogelijke delers tot en met de vierkantswortel van het getal. De zeef van Eratosthenes vindt alle primes tot een grens. Voor grote getallen bestaan deterministische testen die correct zijn tot bepaalde grenzen en probabilistische testen zoals Miller-Rabin die met hoge kans een getal als priem aanduiden. De AKS-primaliteitstest is deterministisch en polynoomtijds, maar praktisch zelden gebruikt.

Primaliteit heeft toepassingen in de getaltheorie en cryptografie. Bij RSA en aanverwante systemen spelen grote priemgetallen een sleutelrol; hun veiligheid berust op de moeilijkheid van factorisatie en op betrouwbare primaliteitstests bij sleutelgeneratie.

De verdeling van primes over de natuurlijke getallen is bestudeerd: volgens de priemgetallenstelling groeit het aantal priemgetallen ≤ n ongeveer als n/log n; de onderlinge afstand tussen opeenvolgende priemgetallen groeit op lange termijn gemiddeld als log n. Enkele bekende kleine priemgetallen zijn: 2, 3, 5, 7, 11, 13.