Qu'est-ce que « Premier » ?

Exemple 29.18 (Application à la cryptographie)

Le théorème de Fermat rend l’exponentiation modulo $n$ réversible lorsque les exposants sont bien choisis — le cœur du cryptosystème RSA. Avec $p, q$ grands premiers et $n = pq$, on publie $n$ et un exposant $e$ ; le chiffrement est $x \mapsto x^e \bmod n$. Déchiffrer requiert un exposant $d$ avec $ed \equiv 1 \pmod{(p-1)(q-1)}$, que seul celui qui connaît $p$ et $q$ peut calculer — et retrouver $p, q$ à partir de $n$ signifie factoriser un nombre de centaines de chiffres, ce qu’aucun algorithme connu ne fait en temps raisonnable.