# Solving discrete logarithm when p is not a safe prime

If you have the cyclic group of integers modulo $p$, where $p$ is not a safe prime, as well as a generator $g$ with which for all factors $q$ of $(p-1)$,

$g^{(p-1)/q} \ne 1$,

This answer says that given $g$ and $g^x \bmod p$, we can determine $x \bmod q$ in $O(\sqrt{q})$ time.

What algorithm lets us do that?

• You may be looking for the Pohlig-Hellman algorithm. By the way, this remains true even if $p$ is a safe prime, but in this case $q$ is sufficiently large for it to not be a problem. – fkraiem Jun 4 '15 at 4:57
• Also you can use Shank's algorithm (it needs $O(\sqrt{q})$ memory) – 111 Jul 20 '15 at 13:55
• @fkraiem and 111 Seems like an answer rather than a comment, could you answer? – Maarten Bodewes Oct 2 '18 at 23:03
• This was 3 years ago. – robertkin Oct 2 '18 at 23:04