The RSA Problem
\[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.
