查看“︁大步小步算法”︁的源代码

{{Expand language|1=ru|time=2020-04-17T10:58:22+00:00}}
在[[群论]]中，'''大步小步算法'''（{{lang-en|baby-step giant-step}}）是{{le|丹尼尔·尚克斯|Daniel Shanks}}发明的一种[[中途相遇攻击|中途相遇]][[算法]]，用于计算[[离散对数]]或者有限[[阿贝尔群]]的[[阶 (群论)|阶]]。<ref>{{cite|author=Daniel Shanks|authorlink=Daniel Shanks|title=Class number, a theory of factorization and genera|work=In Proc. Symp. Pure Math.|volume=20|pages=415—440|publisher=American Mathematical Society|location=Providence, R.I.|year=1971|language=en}}</ref>其中离散对数问题在[[公钥加密]]领域有着非常重要的地位。

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

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

给出一个 <math>n</math> [[阶 (群论)|阶]][[循环群]] <math>G</math> 、该群的一个[[群的生成集合|生成元]] <math>\alpha</math> 和一个元素 <math>\beta</math> 。试找到一个整数 <math>x</math> 满足 
: <math>\alpha^x = \beta\,.</math>

大步小步算法把 <math>x</math> 代换成：
:<math>x = im + j</math>
:<math>m = \left\lceil \sqrt{n} \right\rceil </math>
:<math>0 \leq i < m</math>
:<math>0 \leq j < m</math>

于是有：
: <math>\alpha^x = \beta\,</math>
: <math>\alpha^{im + j} = \beta\,</math>
: <math>\alpha^j = \beta\left(\alpha^{-m}\right)^i\,</math>

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

== 算法 ==
给出C++17版本的代码：
<syntaxhighlight lang="c++">
#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;
}
</syntaxhighlight>

== 延伸阅读 ==
* [[Henri Cohen (number theorist)|H. Cohen]], A course in computational algebraic number theory, Springer, 1996.
* [[Daniel Shanks|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.
* [[Andrew Sutherland (mathematician)|A. V. Sutherland]], [http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf Order computations in generic groups]{{Wayback|url=http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf |date=20191127011419 }}, 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}}

== 参考资料 ==
{{reflist}}

[[分类:算法]]
[[分类:群论]]