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

  • 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

1

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

0

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

  • 0
    Oh my bad I forgot a symbol it should be x^e mod p my mistake...2011-03-18