Applications to cryptography rely on the disparity in computer time required to find large primes and to factor large integers.

For example, a code maker chooses two large primes $p$ and $q$ of about 400 decimal digits each. Procedures for finding such primes require very little computer time. The primes are kept secret but their product $n=pq$, an 800-digit number, is made public. For this reason, these are often called public key codes. Messages are coded by a method (described below) that requires only the knowledge of $n$. But to decode, both factors $p$ and $q$ must be known. With the most efficient computer techniques devised to date (2010), factoring an 800-digit number may require billions of years on a single computer. For this reason, the codes are considered unbreakable, at least with the current state of knowledge on factoring large numbers.

To code a message by this method, we replace each letter by two digits, say $A=01$, $B=02$, $\mathrm{\dots}$, $Z=26$, and divide the message into pieces of convenient length smaller than the public value $n=pq$. Choose a prime $r$ that does not divide either $p-1$ or $q-1$. Like $n$, the prime $r$ is made public. To code a piece $x$, raise $x$ to the power $r$ and reduce ${x}^{r}$ modulo $n$ to obtain an integer $y$ (the coded form of $x$) between $1$ and $n$. Thus, $y\equiv {x}^{r}\phantom{\rule{0.949em}{0ex}}(modn)$ and $$.

To decode, we must recover $x$ from $y$. To do this, let $s$ denote the reciprocal of $r$ modulo $\varphi \left(n\right)$, so that $rs=1+t\varphi \left(n\right)$ for some integer $t$. (Here $\varphi \left(n\right)$ is Euler’s totient (§27.2).) By the Euler–Fermat theorem (27.2.8), ${x}^{\varphi \left(n\right)}\equiv 1\phantom{\rule{0.949em}{0ex}}(modn)$; hence ${x}^{t\varphi \left(n\right)}\equiv 1\phantom{\rule{0.949em}{0ex}}(modn)$. But ${y}^{s}\equiv {x}^{rs}\equiv {x}^{1+t\varphi \left(n\right)}\equiv x\phantom{\rule{0.949em}{0ex}}(modn)$, so ${y}^{s}$ is the same as $x$ modulo $n$. In other words, to recover $x$ from $y$ we simply raise $y$ to the power $s$ and reduce modulo $n$. If $p$ and $q$ are known, $s$ and ${y}^{s}$ can be determined (mod $n$) by straightforward calculations that require only a few minutes of machine time. But if $p$ and $q$ are not known, the problem of recovering $x$ from $y$ seems insurmountable.