¿Qué es Primo?

Ejemplo 29.18 (Aplicación a la criptografía)

El teorema de Fermat hace reversible la exponenciación módulo $n$ cuando los exponentes se eligen adecuadamente: ese es el corazón del criptosistema RSA. Con $p, q$ primos grandes y $n = pq$, se publican $n$ y un exponente $e$; cifrar es $x \mapsto x^e \bmod n$. Descifrar exige un exponente $d$ con $ed \equiv 1 \pmod{(p-1)(q-1)}$, que solo puede calcular quien conozca $p$ y $q$; y recuperar $p$ y $q$ a partir de $n$ significa factorizar un número de cientos de cifras, cosa que ningún algoritmo conocido hace en un tiempo razonable.