大步小步算法

在群论中，大步小步算法（英语：baby-step giant-step）是丹尼尔·尚克斯（英语：Daniel Shanks）发明的一种中途相遇算法，用于计算离散对数或者有限阿贝尔群的阶。其中离散对数问题在公钥加密领域有着非常重要的地位。

许多常用的加密系统都基于离散对数极难计算这一假设——计算越困难，这些系统提供的数据传输就越安全。增加离散对数计算难度的一种方法，是把密码系统建立在更大的群上。

这是一种空间换时间（英语：space–time tradeoff）的算法，实质上是求解离散对数的朴素算法（枚举并试乘）的一个相当简单的改进。

给出一个 ${\displaystyle n}$ 阶循环群 ${\displaystyle G}$ 、该群的一个生成元 ${\displaystyle \mathrm{\alpha <!--\; \alpha \; -->}}$ 和一个元素 ${\displaystyle \mathrm{\beta <!--\; \beta \; -->}}$ 。试找到一个整数 ${\displaystyle x}$ 满足

大步小步算法把 ${\displaystyle x}$ 代换成：

于是，我们有：

该算法先对 ${\displaystyle j}$ 的不同取值计算出 ${\displaystyle {\mathrm{\alpha <!--\; \alpha \; -->}}^j}$ 的值，然后固定一个 ${\displaystyle m}$ ，并对 ${\displaystyle i}$ 尝试不同的取值,带入上面同余式的右边，看是否与某个（已经预先算出的）同余式左边的值相匹配。

给出C++17版本的代码：