## The RSA Problem

Suppose we are given positive integers
$e, N$
, and
$a^e \pmod{N}$
for some unit
$a$
. How can we recover
$a$
?
One strategy is to find an integer
$d$
such that
$a^{d e} = a \pmod{N}$
. By Euler’s Theorem,
$d$
will satisfy this equation if
$d e = k \phi(N) + 1$
for some
$k$
. In other words, we compute
$\pmod{\phi(N)}$
and compute
$(a^e)^d$
to recover
$a$
.
However it is not known how to compute
$\phi(N)$
from
$N$
without factoring
$N$
, and it is not known how to factor large numbers efficiently.