What is Prime?

Example 29.18 (Application to cryptography)

Fermat’s theorem makes exponentiation modulo $n$ reversible when the exponents are chosen suitably — the heart of the RSA cryptosystem. With $p, q$ large primes and $n = pq$, one publishes $n$ and an exponent $e$; encryption is $x \mapsto x^e \bmod n$. Decrypting requires an exponent $d$ with $ed \equiv 1 \pmod{(p-1)(q-1)}$, which only someone knowing $p$ and $q$ can compute — and recovering $p, q$ from $n$ means factoring a number hundreds of digits long, which no known algorithm does in reasonable time.