0
$\begingroup$

Can the Shanks algorithm for discrete logarithm problem (baby-step/giant-step) be used for composite orders?

According to Wiki, "Usually the baby-step giant-step algorithm is used for groups whose order is prime. If the order of the group is composite then the Pohlig–Hellman algorithm is more efficient."

Is the above statement true? I have been trying to understand why the Shanks algorithm may not be used for composite orders, but I have not been able to figure out the reason.

$\endgroup$
4
  • $\begingroup$ Shanks algorithm can only be used for one piece functions, are you aware of this? $\endgroup$
    – Asinomás
    Dec 30, 2016 at 18:10
  • $\begingroup$ Not really, could you please elaborate? $\endgroup$
    – user24720
    Dec 30, 2016 at 18:12
  • $\begingroup$ it was a joke about a famous manga. $\endgroup$
    – Asinomás
    Dec 30, 2016 at 18:13
  • $\begingroup$ ahh :D wasn't aware of that till I accidentally searched "Shanks" instead of "Shanks Algorithm" $\endgroup$
    – user24720
    Dec 30, 2016 at 18:15

1 Answer 1

Reset to default
1
$\begingroup$

Shank's algorithm can be used for any group, it does not use any specific properties. The same is true for the Pohlig-Hellman algorithm. Suppose we have a group of order $$r=\prod_ip_i^{e_i},$$ then Shank's algorithm is usually presented to have complexity $O(\sqrt{r})$ (although it really is a time-memory trade-off) while Pohlig-Hellman has complexity $$O\left(\sum_ie_i(\log{r}+\sqrt{p_i})\right).$$ Note that Pohlig-Hellman generally does better for composite order, so there is little reason to use Shank's in that case. For prime order groups Pohlig-Hellman doesn't really do anything, so you can just use Shank's.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.