# How to compare the order of elements in cyclic groups?

In a cyclic group with randomly looking behavior like the one used in secp256k1, is there any known efficient algorithm to compare the order of two randomly given elements $$P_1$$ and $$P_2$$ and find out which one will appear first starting from a known generator point of the cycle? If such algorithm exists, would that be considered a weakness?!

Consider that we have two known integers $$a$$ and $$b$$ so that $$a>b$$. Taking $$P_1=a\times G$$ and $$P_2=b\times G$$ we can say $$P_2$$ has a greater order in the cycle, meaning that starting from the generator point it will appear before than $$P_1$$.

By this definition is there any known algorithm based which one can compare the order of two random elements of the group $$P_1$$ and $$P_2$$?

• You really shouldn't use the word "order" here. "Order" in group theory has a precise meaning, and using it to mean anything else creates confusion. Commented Jan 6, 2019 at 13:04
• What word do you suggest to use instead of "order"? Commented Jan 6, 2019 at 16:15
• The integer $a$ such that $P_1 = a\cdot G$ is called the discrete logarithm of $P_1$ (relative to $G$), and similarly for $P_2$, so you could say that you wish to show that the discrete logarithm of $P_2$ is larger than that of $P_1$. Commented Jan 6, 2019 at 16:21

By this definition is there any known algorithm based which one can compare the order of two random elements of the group $$P_1$$ and $$P_2$$?

No, such an algorithm would allow for an easy break of the elliptic curve discrete logarithm problem. But as this problem is assumed hard for secure curves like secp256k1 us knowing such an algorithm is impossible.

To see this fix the reference generator $$G$$ to the standard one for the curve with the generator having order $$q$$. Furthermore let $$P=xG$$ be the challenge point for which we want to recover $$x$$. Now define $$a=1$$ and $$b=q-1$$.

1. Compute $$m=\frac{a+b}{2}$$ and $$M=mG$$.
2. Check whether $$M=P$$ and if so, return $$m$$.
3. Check whether $$M using the conjectured algorithm. If this is true, set $$a\gets m$$, otherwise set $$b\gets m$$.
4. Go to 1.

This is a standard binary search as you may have recognized and it will find the discrete logarithm in about $$\log_2 q$$ scalar point multiplications and algorithm evaluations which is quite efficient.

• And, best known algorithms for ECDLP are baby-step giant-step and Pollard's rho and these requires $\mathcal{O}\sqrt{n}$ comlexity. Commented Jan 6, 2019 at 13:07