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
    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