大步小步算法

此條目可参照俄語維基百科和英語維基百科相應條目来扩充。 (2020年4月17日) 若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

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

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

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

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

${\displaystyle \alpha ^{x}=\beta \,.}$

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

${\displaystyle x=im+j}$

${\displaystyle m=\left\lceil {\sqrt {n}}\right\rceil }$

${\displaystyle 0\leq i<m}$

${\displaystyle 0\leq j<m}$

于是有：

${\displaystyle \alpha ^{x}=\beta \,}$

${\displaystyle \alpha ^{im+j}=\beta \,}$

${\displaystyle \alpha ^{j}=\beta \left(\alpha ^{-m}\right)^{i}\,}$

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

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

#include <cmath>
#include <cstdint>
#include <unordered_map>

std::uint32_t pow_m(std::uint32_t base, std::uint32_t exp, std::uint32_t mod) {
        // 这里需要实现快速幂算法
}


///计算满足 g^x % mod == h 的x
std::optional<std::uint32_t> babystep_giantstep(std::uint32_t g, std::uint32_t h, std::uint32_t mod) {
        const auto m = static_cast<std::uint32_t>(std::ceil(std::sqrt(mod)));
        auto table = std::unordered_map<std::uint32_t, std::uint32_t>{};
        auto e = std::uint64_t{1}; // 临时值可能大于32位整数的范围
        for (auto i = std::uint32_t{0}; i < m; ++i) {
                table[static_cast<std::uint32_t>(e)] = i;
                e = (e * g) % mod;
        }
        const auto factor = pow_m(g, mod-m-1, mod);
        e = h;
        for (auto i = std::uint32_t{}; i < m; ++i) {
                if (auto it = table.find(static_cast<std::uint32_t>(e)); it != table.end()) {
                        return {i*m + it->second};
                }
                e = (e * factor) % mod;
        }
        return std::nullopt;
}

加速大步小步算法的最佳方式，是使用高效的表格查找機制。在此情況下，最適合的是使用雜湊表（hash table）。雜湊是針對第二個元件（即元素對的第二個值）進行，並且在主迴圈的第 1 步中，會對 γ 做雜湊，然後檢查對應的記憶體位置。由於雜湊表可以在 ${\displaystyle O(1)}$（常數時間）內進行新增與查詢操作，因此這個過程不會拖慢整體的大步小步算法。

此演算法的空間複雜度為 ${\displaystyle O({\sqrt {n}})}$，而時間複雜度則為 ${\displaystyle O({\sqrt {n}})}$。這樣的執行時間比起暴力的 ${\displaystyle O(n)}$ 執行時間來得更優。

當模數是一個不是太大的質數時，竊聽者可以使用大步小步算法來推導在Diffie–Hellman金鑰交換中產生的私鑰。如果模數不是質數，則可以使用Pohlig–Hellman演算法，其演算法複雜度更低，也有可能解出相同的問題。 ^[2]

• H. Cohen, A course in computational algebraic number theory, Springer, 1996.
• D. Shanks, Class number, a theory of factorization and genera. In Proc. Symp. Pure Math. 20, pages 415—440. AMS, Providence, R.I., 1971.
• A. Stein and E. Teske, Optimized baby step-giant step methods, Journal of the Ramanujan Mathematical Society 20 (2005), no. 1, 1–32.
• A. V. Sutherland, Order computations in generic groups（页面存档备份，存于互联网档案馆）, PhD thesis, M.I.T., 2007.
• D. C. Terr, A modification of Shanks’ baby-step giant-step algorithm, Mathematics of Computation 69 (2000), 767–773. doi:10.1090/S0025-5718-99-01141-2