Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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
show 1 more comment

Your Answer

 
discard

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.