# How does the order of Q affect the time it takes to solve ECDLP?

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?

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