# Given $p$, $e$, and $m^e$ mod $p$, compute $m$ mod $p$?

Is it possible to compute $m$ mod $p$, if you are given $p$, $e$, and $m^e$ mod $p$?

$p$ is prime. $(p-1)$ and $e$ are relatively prime.

-

compute $d$ such that $ed\equiv 1\pmod {p-1}$, then $(m^e)^d\equiv m^{ed}\equiv m^{k(p-1)+1}\equiv (m^{p-1})^k.m\equiv m\pmod p$.
Thus, after computing such $d$ just calculate $(m^e)^d\pmod p$ and that will give you the desired answer.
But what if no such d exists? For example, given $e=3$ and $p=13$. $3d \equiv 1 ($mod$12)$. gcd(12,3) is not 1 so no such multiplicative inverse d exists. – Takkun Sep 3 '12 at 19:18
@Takkun : notice how Avatar never used the fact that $(p,e) = 1$. The right condition for existence would be $(p-1,e) = 1$. Maybe there's another trick but I can't see it just like that. – Patrick Da Silva Sep 3 '12 at 19:23
@Takkun : It seems like a better condition to impose, because you want the exponent to be relatively prime to the order of the cyclic group which is $p-1$. Otherwise you have multiple options, i.e. the function $m \mapsto m^e$ is not an injective function of $m$ from $\mathbb F_p$ to $\mathbb F_p$. – Patrick Da Silva Sep 3 '12 at 19:24
Question: where does the $k$ come from? – Takkun Sep 3 '12 at 20:02