2
$\begingroup$

I use Sagemath's built-in function discrete_log() to solve ECDLP and according to the documentation it uses Pohling-Hellman algorithm to solve an ECDLP.

This is the case for my EC:

P-order => 176648753626148987385153422443570230330
Q-order() => 2

The P-order has these prime factors: 2 * 3 * 5 * 5888291787538299579505114081452341011

Even though the highest prime factor is super-large, the ECDLP through discrete_log() is solved within a second.

I Read about the Pohling-hellman attack and it only mentions that P should have small prime-factors in order for the attack to be successful. It never mentions the order of Q.

How does the order of Q affect the time it takes for the attack to be successful?

$\endgroup$
2
$\begingroup$

Here is what I believe Sagemath is doing:

  • Given the problem of finding $x$ s.t. $xP = Q$, one step is computing $x' = x \bmod 5888291787538299579505114081452341011$; it does this by computing $P' = (2\cdot 3 \cdot 5)P$, and $Q' = (2 \cdot 3 \cdot 5)Q$, and trying to solve $x'P' = Q'$

  • As the order of $P'$ is circa $2^{122}$, we would normally expect this computation to take circa $2^{61}$ time (quite a while). However, in this case, $Q'$ is the neutral element. I suspect that Sagemath notices this, and so immediately concludes that $x' = 0$

  • Every other computation involved in Pohlig-Hellman is relatively quick, and so it reports the answer ($3 \cdot 5 \cdot 5888291787538299579505114081452341011$) quickly.

The summary is: if your implementation special cases this $Q' = 0$ case, then we can skip any prime that does not appear in the order of $Q$; the time taken by Polhig-Hellman is dominated by the largest prime that appears both in the order of $P$ and the order of $Q$.

$\endgroup$
  • $\begingroup$ Thanks for shedding light on this. This is exactly what I wanted to know because in literature it's always mentioned only the order of P. Your answer makes complete sense, especially considering that I had another case where the order of Q was very large and even though the prime factors were small, it took way more time to compute the discrete log. $\endgroup$ – exonxon Oct 22 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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