大步小步算法

在群論中，大步小步算法（英語：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;
}

延伸閱讀

• 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

參考資料

1. 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 （英語）