# Shanks Algorithm for composite orders

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.

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

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.