/(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}/) 算法的流程如下：
- 将原式做如下操作：
/[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)
/]
-
易得 /(k /leq /sqrt{q}/)，/(b /leq /sqrt{q}/)。
-
我们枚举每一个 /(k/) ，将 /(a ^ {k /left /lfloor/sqrt{p}/right/rfloor}/) 的值存到一个 /(hash/) 里面，然后在枚举 /(b/)，判断 /(hash/) 中是否存在即可。
时间复杂度 /(O(/sqrt{q})/)。
原创文章，作者：Carrie001128，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/275682.html