BSGS 算法解决的是一类问题，即$$g^x\equiv h \pmod p$$
已知 求 。这就是 DLP ，即离散对数问题。
BSGS 的想法是把指数 拆成两个部分 $$x=im+j$$
这样原式变成$$g^{im+j}\equiv h \pmod p$$
也就是$$(g^m)^i\equiv h\cdot g^{-j}\pmod p$$
于是我们可以先把左边所有的 存起来
然后枚举右边所有的
两边一旦撞上，就得到解
算法步骤
要解$$g^x\equiv h \pmod p$$
第一步，选取步长
取$$m=\lceil \sqrt n \rceil$$
第二步，预处理 giant steps
计算并存表$$(g^m)^0, (g^m)^1, (g^m)^2, \dots, (g^m)^{m-1}$$
把”值->指数 “存进哈希表
第三步，枚举 baby steps
依次计算$$h, hg^{-1}, hg^{-2}, \dots, hg^{-(m-1)}$$
如果某个值在哈希表中出现了，说明$$(g^m)^i \equiv hg^{-j} \pmod p$$
于是$$g^{im+j} \equiv h \pmod p$$
所以答案就是 $$x = im + j$$