Computing the discrete log in cyclic group $G$

85 Views Asked by At

Given a cyclic group such that $g_1, g_2, g_3,...,g_p$ is element in $G$, how would one go about computing the discrete log in cyclic group $G$, if the output of $O(g_1) = O(g_2)$ and $g_1$ is not equal to $g_2$. So in other words, for example, $g_1=2$ and $g_2=5$. Obviously $2$ is not equal to $5$, but the output $O(g_1)$ is equal to say $10$ and the output $O(g_2)$ is also equal to $10$.

With this in mind, how would we go about computing the discrete log in cyclic group $G$?

1

There are 1 best solutions below

1
On

Well, there are several algorithms to attack discrete logs: baby-step giant-step, Pollards rho- and lambda-method, and Pohlig-Hellman.

For elliptic curves, the MOV algorithm is very useful as it reduces the discrete log problem for EC to the discrete log problem for fields of the form $GF(q^m)$ (which has a cyclic multiplicative group), especially $m=2$ if the curve is super-singular.