finding $m$ from $c = m^e \pmod{n}$

Question

I'm working through an RSA encryption example, and I'm being asked to solve $c = m^e \pmod{n}$ for $m$ given c, e, and n (along with its factorization.). Since I already have that information provided, is it at all necessary to work through the decryption function? If not, is there any straightforward way to solve for $m$ without use of a computer?

Answer 1

Given the factorisation of $n$, this is possible. Without it, the task is close to impossible.

So, say we have that $n=pq$, so we can compute this value $\phi(n)=(p-1)(q-1)$. From there, compute the inverse of $e$ modulo $\phi(n)$, that is, use the extended euclidean algorithm to find $d>0$ such that $$de+k\phi(n)=1.$$

Then, to recover $m$, simply compute $c^d\mod n$. You may check that $m$ is correct by checking that $m^e=c^{de}=c$.

(I'm assuming you know how RSA works, if not, let me know in the comments.)