Wat is Priem?

Voorbeeld 29.18 (Toepassing in de cryptografie)

De stelling van Fermat maakt het machtsverheffen modulo $n$ omkeerbaar zodra de exponenten geschikt gekozen zijn — het hart van het RSA-cryptosysteem. Met grote priemgetallen $p$ en $q$ en $n = pq$ publiceer je $n$ en een exponent $e$; versleutelen is $x \mapsto x^e \bmod n$. Ontsleutelen vraagt een exponent $d$ met $ed \equiv 1 \pmod{(p-1)(q-1)}$, en die kan alleen berekend worden door wie $p$ en $q$ kent — en $p$ en $q$ uit $n$ terugvinden betekent een getal van honderden cijfers ontbinden, wat geen enkel bekend algoritme in redelijke tijd doet.