Period finding enables solving the Discrete Logarithm Problem

50 Views Asked by At

Does being able to find the periods enable us to solve the Discrete Logarithm Problem (DLP)?

This is what I have got so far:

Let $G$ be a finite cyclic group with $G = \langle g \rangle$, i.e. $g \in G$ is a generator of $G$. Let further be $h \in G$ such that $h = g^k$ for some $k \in \mathbb{Z}$. Suppose that we know that $p_1$ and $p_2$ are the periods of $g$ and $h$, i.e. $p_1$ and $p_2$ are the smallest integers such that

$$g^{p_1} = 1 \text{ and } h^{p_2} = 1.$$

Then we have that $$g^{kp_2+p_1} = g^0$$ $$\Longrightarrow kp_1 + p_2 \equiv 0 \pmod{ \lvert G \rvert}$$ $$\Longrightarrow kp_1 \equiv -p_2 \pmod{ \lvert G \rvert}.$$

However, I am not sure if we can write $k = -p_2 p_1^{-1} \bmod{ \lvert G \rvert}$, since I am not sure I am not sure that $\gcd(p_1, \lvert G \rvert) = 1$ holds. Could you please help me?