Baby_Step_Gaint_Step(BSGS) 算法

本文主要是介绍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. 将原式做如下操作：

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})\)。

这篇关于Baby_Step_Gaint_Step(BSGS) 算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！