When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time. But I also read that there are several algorithms in $\mathcal{O}(\sqrt{n})$, for instance, the Shank's baby-step/giant-step so there must be some misunderstanding by me.
- What is the assumption?
If I understand the problem correctly, we are given a group with a modulus and a generator of that group. The problem is:
- Given an element $x$ of the group, find the number $a$ so that the generator $g$ will generate $x$ by $$x = g^a \bmod q.$$ And the assumption is that we cannot do it for a random or worst instance of the problem in polynomial time, but I must have misunderstood because I read about deterministic algorithms such as Shank's baby-step/giant-step which solve the problem in $\mathcal{O}(\sqrt{|G|})$ which is quite fast isn't it?
Where is my mistake?