0
$\begingroup$

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

  • 2
    Take a look at the Extended Euclidean algorithm at http://en.wikipedia.org/wiki/Euclidean_algorithm2011-03-18
  • 0
    possible duplicate of [How to find the inverse modulo m?](http://math.stackexchange.com/questions/25390/how-to-find-the-inverse-modulo-m)2011-03-18
  • 0
    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$.2011-03-18
  • 0
    @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\:.$2011-03-18
  • 0
    @Ross, @Elvind, @Bill: I've edited the question in light of the comment Naan made to the answer below.2011-03-19
  • 0
    Also posted here: http://math.stackexchange.com/questions/27867/modular-arithmetic/2011-03-19
  • 0
    **Note:** The question has changed from solving $\rm\ e\ x \equiv d\ (mod\ p)\ $ to solve $\rm\ x^e \equiv d\ (mod\ p)\:.\ $ The above comments and one of the answers were written before the question was changed.2011-03-20

2 Answers 2