Priemgetal

Een priemgetal is een geheel getal groter dan 1 waarvan de enige factoren 1 en zichzelf zijn. Een factor is een geheel getal dat gelijkmatig in een ander getal kan worden gedeeld. De eerste paar priemgetallen zijn 2, 3, 5, 7, 11, 13, 17, 19, 23 en 29. Getallen die meer dan twee factoren hebben, worden samengestelde getallen genoemd. Het getal 1 is noch priem noch samengesteld. 

Priemgetallen kunnen om een aantal redenen worden gebruikt. Voor sommige vormen van cryptografie worden bijvoorbeeld priemgetallen gebruikt.

Voor elk priemgetal, bijvoorbeeld "p", bestaat er een priemgetal dat groter is dan p, p' genaamd.  Dit wiskundige bewijs, dat al in de oudheid werd gedemonstreerd door de Griekse wiskundige Euclides, valideert het concept dat er geen "grootste" priemgetal bestaat. Naarmate de verzameling natuurlijke getallen N = {1, 2, 3, ...} groter wordt, komen priemgetallen over het algemeen minder vaak voor en zijn ze moeilijker te vinden in een redelijke hoeveelheid tijd. 

Hoe bepaal je of een getal priem is

Een computer kan worden gebruikt om extreem grote getallen te testen om te zien of ze priem zijn.Maar omdat er geen limiet is aan hoe groot een natuurlijk getal kan zijn, komt er altijd een punt waarop het testen op deze manier een te grote opgave wordt -- zelfs voor de krachtigste supercomputers. Als voorbeeld: het grootst bekende priemgetal in december van 2018 was 24.862.048 cijfers.

Verschillende algoritmes zijn geformuleerd in een poging om steeds grotere priemgetallen te genereren. Stel bijvoorbeeld dat  "n" een geheel getal is, en het is nog niet bekend of n priem of samengesteld is. Neem eerst de vierkantswortel -- of de 1/2 macht -- van n; rond dit getal dan af naar boven tot het volgende hoogste gehele getal en noem het resultaat m.  Vind dan alle volgende quotiënten:

qm = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2

Het getal n is priem als -- en alleen als -- geen van de q's, zoals hierboven afgeleid, gehele getallen zijn.

Mersenne- en Fermat-priemgetallen

Een Mersenne-priemgetal is een getal dat herleidbaar moet zijn tot de vorm 2 n - 1, waarbij n een priemgetal is. De eerste paar bekende waarden van n die Mersenne-priemgetallen opleveren zijn waar n = 2, n = 3, n = 5, n = 7, n = 13, n = 17, n = 19, n = 31, n = 61, en n = 89.

Een Fermatpriem is een Fermatgetal dat ook priem is. Een Fermat-getal F n is van de vorm 2 m + 1, waarbij m de macht van 2 betekent -- dat is, m = 2 n, en waarbij n een geheel getal is.

Prime numbers and cryptography

Encryptie volgt altijd een fundamentele regel: het algoritme -- of de eigenlijke procedure die wordt gebruikt -- hoeft niet geheim te blijven, maar de sleutel wel. Priemgetallen kunnen heel nuttig zijn om sleutels te maken. De kracht van openbare/privésleutelversleuteling ligt bijvoorbeeld in het feit dat het product van twee willekeurig gekozen priemgetallen gemakkelijk te berekenen is. Het kan echter erg moeilijk en tijdrovend zijn om te bepalen welke twee priemgetallen zijn gebruikt om een extreem groot product te maken, als alleen het product bekend is.

In RSA (Rivest-Shamir-Adleman), een bekend voorbeeld van cryptografie met openbare sleutels, worden priemgetallen altijd verondersteld uniek te zijn. De priemgetallen die worden gebruikt in de Diffie-Hellman sleuteluitwisseling en de Digital Signature Standard (DSS) cryptografieschema's, zijn echter vaak gestandaardiseerd en worden door een groot aantal toepassingen gebruikt.