Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this 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
Actually I think this is my mistake. Doesn't e have to be relatively prime to (p-1) not p? Edit: Yup thanks Patrick Da Silva, I thought I messed that up. – Takkun 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.