I have ElGamal signature scheme implemented in finite field $\mathbb{F}_p$. The thing is that I need to apply Pollard's Rho Method on elliptic curve $E(\mathbb{F}_p)$ to this scheme, solve discrete logarithm problem and find private key $x$. In ElGamal scheme I have $a^x\equiv b\ (mod\ p)$ where $a,\ b\in \mathbb{F}_p$ and in Pollard's Rho Method I have $Q=dP$ where $P,Q\in E(\mathbb{F}_p)$.
So how can I get $P,\ Q$ from $a,\ b$ and, after I get $d$, how can I get $x$ from it?
Is it even possible or am I totally wrong?


2 Answers 2


In the question you said that $a^x\equiv b\ (mod\ p)$ and $P,Q\in E(\mathbb{F}_p)$. In general case, the number of elliptic curve points $\#E(\mathbb{F}_p)$ is not equal to $p$. So these two groups are not isomorphic and your question is wrong.

If $\#E(\mathbb{F}_p)=p$ the curve is called anomalous and we can find the map $\psi : E(\mathbb{F}_p) \to \mathbb{Z}_p$ in polynomial time. In this state, $a=\psi(P),b=\psi(Q)$ and $x=d$.

The main idea behind Pollard’s rho algorithm is to find distinct pairs $(c' , d' )$ and $(c'' , d'' )$ of integers modulo $n$ such that $c' P + d' Q = c'' P + d'' Q$. So $(c' − c'' ) = (d'' − d' )d \pmod n$. Hence $d$ can be obtained by computing $$d = (c' − c'' )(d'' − d' )^{ −1} \pmod n.$$

For more details you can see page $156,168$ of "Guide to elliptic curve cryptography", Hankerson, ....

  • $\begingroup$ Thank you for your reply! That makes sense. I'm gonna ask my teacher about that. I guess I can count your reply as an answer. $\endgroup$ Commented Apr 30, 2017 at 16:19

Pollard's Rho Method is a general method for finding discrete logarithms in a finite group. It doesn't use any of the properties of Elliptic Curves.

So just use the same algorithm, over the multiplicative group of $\mathbb F_p$ instead of $E(\mathbb F_p)$.

  • $\begingroup$ Thanks for the quick reply! Unfortunately, according to the task, I have to use Pollard's Rho Method on elliptic curves. $\endgroup$ Commented Apr 30, 2017 at 11:42
  • $\begingroup$ @GlebIgnatieff: If you say so. But it makes no sense. $\endgroup$
    – TonyK
    Commented Apr 30, 2017 at 14:27
  • $\begingroup$ Well, I guess there is some misunderstanding between me and my teacher... $\endgroup$ Commented Apr 30, 2017 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.