O que é Primo?

Exemplo 29.18 (Aplicação à criptografia)

O teorema de Fermat torna reversível a exponenciação módulo $n$ quando os expoentes são bem escolhidos — o coração do criptossistema RSA. Com $p, q$ primos grandes e $n = pq$, publicam-se $n$ e um expoente $e$; a cifragem é $x \mapsto x^e \bmod n$. Decifrar exige um expoente $d$ com $ed \equiv 1 \pmod{(p-1)(q-1)}$, que só quem conhece $p$ e $q$ consegue calcular — e recuperar $p, q$ a partir de $n$ significa fatorar um número de centenas de algarismos, o que nenhum algoritmo conhecido faz em tempo razoável.