The RSA Problem

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