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.

How would you find $x$ in a modulo arithmetic expression $x^e \bmod p$ knowing only $e$ and $p$?

$e$ is an integer, $0 \leq e \lt p$, that is relatively prime to $p-1$; and $x$ is an integer, $0 \leq x < p$.

share|improve this question
2  
Take a look at the Extended Euclidean algorithm at en.wikipedia.org/wiki/Euclidean_algorithm –  Ross Millikan Mar 18 '11 at 21:51
    
possible duplicate of How to find the inverse modulo m? –  Bill Dubuque Mar 18 '11 at 21:55
    
I don't think the question is a duplicate, it is a different question after all. But a good solution to this problem would be to find the inverse modulo $p$. –  please delete me Mar 18 '11 at 22:07
    
@Eivind: They are equivalent: any method that solves $\rm\ e\ x \equiv d\ (mod\ p)\ $ can solve the special case $\rm\ d\equiv 1\ $ so it can compute $\rm 1/e\:.\ $ Conversely any method that can compute $\rm\ 1/e\ $ can solve the equation by scaling the equation by $\rm\ 1/e\:.$ –  Bill Dubuque Mar 18 '11 at 22:35
    
@Ross, @Elvind, @Bill: I've edited the question in light of the comment Naan made to the answer below. –  Arturo Magidin Mar 19 '11 at 1:51
show 2 more comments

2 Answers 2

Having fixed the problem: this is still a problem of using the extended Euclidean algorithm.

Because $e$ and $p-1$ are relatively prime, using the Euclidean algorithm you can find integers $r$ and $s$ such that $er + (p-1)s = 1$.

Now, from Fermat's Little Theorem, you should know that $x^{p-1} \equiv 1\pmod{p}$.

So, take $x^e$, and raise it to the $r$th power. We have: \begin{align*} (x^e)^r &\equiv x^{er} \pmod{p}\\ &= \equiv x^{1-(p-1)s} \pmod{p}\\ &\equiv x(x^{p-1})^{-s}\pmod{p}\\ &\equiv x(1)^{-s}\pmod{p}\\ &\equiv x\pmod{p}. \end{align*}

share|improve this answer
add comment

If I understand you correctly, your setup is $xe \equiv c (\text{mod} p)$ and you want to find $x$ given $e$ and $c$.

In general, I believe you need that $e$ and $c$ are relatively prime to $p$, so that these are elements of the group of units of $\mathbb{Z}/p\mathbb{Z}$. In this case, you can find a multiplicative inverse of $[e]^{-1}$ of $[e]$, the residue class of $e$. Using this we can see $[e]^{-1}[x][e] = [x] = [e]^{-1}[c]$ thus the residue class $[x]$ of $x$ is the same as the residue class $[e]^{-1}[c]$ and so we can take the representative of this class satisfying $0$ ≤ $x < p$ which necessarily exists and is unique.

Note: In case you aren't familiar with the terms above, the residue class of a number $x$ is in this case the set of numbers $y$ satisfying $y \equiv x (\text{mod} p)$, and the relation $x \equiv y (\text{mod} p)$ means that $x \text{mod} p = y \text{mod} p$.

share|improve this answer
    
Oh my bad I forgot a symbol it should be x^e mod p my mistake... –  user8442 Mar 18 '11 at 22:38
add comment

Your Answer

 
discard

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