维基百科
大步小步算法
此條目可参照俄語維基百科相應條目来扩充。 (2020年4月17日) |
在群论中,大步小步算法(英語:baby-step giant-step)是丹尼尔·尚克斯发明的一种中途相遇算法,用于计算离散对数或者有限阿贝尔群的阶。[1]其中离散对数问题在公钥加密领域有着非常重要的地位。
许多常用的加密系统都基于离散对数极难计算这一假设——计算越困难,这些系统提供的数据传输就越安全。增加离散对数计算难度的一种方法,是把密码系统建立在更大的群上。
理论 编辑
这是一种空间换时间的算法,实质上是求解离散对数的朴素算法(枚举并试乘)的一个相当简单的改进。
给出一个 阶循环群 、该群的一个生成元 和一个元素 。试找到一个整数 满足
大步小步算法把 代换成:
于是有:
该算法先对 的不同取值计算出 的值,然后固定一个 ,并对 尝试不同的取值,带入上面同余式的右边,看是否与某个(已经预先算出的)同余式左边的值相匹配。
算法 编辑
给出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; }
延伸阅读 编辑
- 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
参考资料 编辑
- ^ Daniel Shanks, Class number, a theory of factorization and genera, In Proc. Symp. Pure Math. 20 (Providence, R.I.: American Mathematical Society), 1971, 20: 415—440 (英语)