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?

  • 1
    $\begingroup$ 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. $\endgroup$ – fkraiem Jun 4 '15 at 4:57
  • $\begingroup$ Also you can use Shank's algorithm (it needs $O(\sqrt{q})$ memory) $\endgroup$ – 111 Jul 20 '15 at 13:55
  • $\begingroup$ @fkraiem and 111 Seems like an answer rather than a comment, could you answer? $\endgroup$ – Maarten Bodewes Oct 2 '18 at 23:03
  • $\begingroup$ This was 3 years ago. $\endgroup$ – robertkin Oct 2 '18 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.