0

Let $p$ be a prime number and let $c \in \mathbb{Z}_p$ and $e \in (\mathbb{Z}/(p-1))^{\ast}$. Put $c \equiv_p m^e$. Find a polynomial time algorithm that given $p$, $e$, and $c$ will compute $m$.

I have tried but failed, I am looking for a complete solution.

Ken
  • 103
  • 1
  • 1
  • 2
Bob
  • 1
  • 1
  • 2
    Think how to invert e in this and easy regular case, and use classical theorems. Remenber Euler ! – Robert NACIRI Feb 18 '15 at 19:15
  • @RobertNACIRI I did but didnt manage :( Can you please help? – Bob Feb 18 '15 at 19:19
  • 2
    I can only help you to find by your self the solution. What is the property of the function modular exponentiation, and what is the link with Euler theorem ?

    Observe that e is relatively prime with (p-1). If you know the group structur of $(\mathbb{Z}/(p-1))^*)$ then remember that every element is invertible. What is the inverse of e in this case, and how to compute it ? When you obtain $d=\frac{1}{e}$ what to do with it?

     – Robert NACIRI Feb 18 '15 at 19:29
  • 1
    The title is misleading, it makes it sound like you don't know what "polynomial time" means when what you are really looking for is a "polynomial time algorithm" for finding m. – mikeazo Feb 18 '15 at 20:14
  • 1
    Hint, more direct than given by Robert NACIRI: How can you efficiently find $d\in\mathbb N$, $d<p-1$, such that $e\cdot d\equiv1\pmod{p-1}$? What can you tell about $c^d\bmod p$, with the help of Fermat's little theorem? Show that the cost of each step in this algorithm is polynomial in the size of $p$ [or of the size of $\max(p,|c|,|e|)$, if the statement is not read as implying that $0\le c<p$ and $0<e<p-1$] – fgrieu Feb 18 '15 at 20:46

0 Answers0