How to compare the order of elements in cyclic groups?

Question

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$?

Answer 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$?

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