The complexity of solving the discrete logarithm problem depends on the choice of the group $G$. A popular choice is $Z_p^*$ where $p$ is a safe prime (${p=2p' +1}$ and $p'$ is also prime). In this case, $G$ is a group of prime order so every element in it is a generator. We can do then:
- Pick ${g}$ as a random element from $Z_p^*$
- Pick a random $x$
- Evaluate ${y = g^x \: mod \: p}$
Now we can assume solving $x = {log_g(y)}$ is hard if $p$ is large enough.
However, I often see the group $G$ is chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm is as follows:
- Pick $g$ as a random element from $Z_N^*$
- Pick $x$ as a random element from $(0, N')$ where ${N' = p' q'}$ where ${p=2p' + 1}$ and ${q=2q' + 1}$
- Evaluate ${y = g^x \: mod \: N}$
This construction is used in various publications from MacKenzie and Fujisaki&Okamoto.
What's that group? Does $Z_N^*$ guarantee computing discrete logarithm is hard? Since ${Z_N^*}$ is not a group of a prime order, is there any guarantee $g$ is a generator?