Baby_Step_Gaint_Step(BSGS) 算法

/(BSGS/) 算法，又称 “北（/(B/)）上（/(S/)）广（/(G/)）深（/(S/)）” 算法，“拔山盖世”算法，可以在 /(O(/sqrt{n})/) 的复杂度内求解离散对数问题。

题目描述：

给定质数 /(p/) 和整数 /(a, n/)，求最小的非负整数 /(m/) ，满足 /(a^m /equiv n(mod/ / p)/) 。

算法分析：

最暴力的算法就是每句每一个 /(m /in [1, p]/) ，看一下有没有一个 /(m/) 满足。时间复杂度 /(O(p)/) 。

因此就需要使用 /(/texttt{BSGS}/) 算法来求解 。

/(/texttt{BSGS}/) 算法的流程如下：

1. 将原式做如下操作：

/[a ^ m /equiv n(mod / / p)
/]

/[a ^ {k /left /lfloor/sqrt{p}/right/rfloor – b} /equiv n (mod / / p)
/]

/[a ^ {k /left /lfloor/sqrt{p}/right/rfloor} /equiv n /times a ^ b(mod / / p)
/]

2. 易得 /(k /leq /sqrt{q}/)，/(b /leq /sqrt{q}/)。

3. 我们枚举每一个 /(k/) ，将 /(a ^ {k /left /lfloor/sqrt{p}/right/rfloor}/) 的值存到一个 /(hash/) 里面，然后在枚举 /(b/)，判断 /(hash/) 中是否存在即可。

时间复杂度 /(O(/sqrt{q})/)。