Originally Posted by

**apsis** I am trying to solve a question for my Number Theory / Intro To Cryptography class. I have been given a question to decrypt a message encoded with the RSA scheme. The encryption with done with a provided n, and e. I am told to compute the d, and to decrypt the message.

In order to compute d I need to compute

$\displaystyle ed \equiv 1 \mod(\phi$ (n))

My issue is that to compute $\displaystyle \phi(n)$ I need to factor n into its original two primes. But this is very hard when n is large (which it is). Is there an easier way to compute $\displaystyle \phi(n)$?

Thanks