## 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.