2
$\begingroup$

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.

1 Answers 1

4

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.

  • 0
    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.2012-09-03
  • 0
    @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.2012-09-03
  • 0
    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.2012-09-03
  • 0
    @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$.2012-09-03
  • 0
    Question: where does the $k$ come from?2012-09-03
  • 0
    Once you have $ed\equiv 1 \pmod {p-1}$, you can write $ed - 1 \equiv 0 \pmod {p-1}$ which just means there is some integer $k$ with $ed-1 = k(p-1)$, and thus $ed = k(p-1) + 1$. But you don't need to calculate $k$ to solve the problem; it was just used to show that the $d$ calculated actually leads you to the result you wanted.2012-09-04