如何用大步小步法求解Pohlig–Hellman分解后的离散对数子问题

首先，先明确我们要解决的子问题：

求解：$g_1^x ≡ h_1 \pmod{p}$
其中：

• $g_1 = 5^{125097} \mod 1000777$（阶为8，因为$g_1^8 = 5^{1000776} ≡ 1 \pmod{p}$，由费马小定理）
• $h_1 = 1000^{125097} \mod 1000777$
• $p = 1000777$（质数）

大步小步法（Baby-step Giant-step）的核心是将未知指数$x$拆分为$x = i \cdot m + j$（其中$m = \lceil \sqrt{n} \rceil$，$n$是$g_1$的阶，这里$n=8$），通过预计算小步值、遍历大步值来匹配解。下面是具体步骤：

步骤1：确定核心参数 #

因为$g_1$的阶$n=8$，计算$m = \lceil \sqrt{8} \rceil = 3$（向上取整平方根，确保覆盖所有可能的解）。

步骤2：预计算「小步表」（Baby-step Table） #

我们先计算$g_1^j \mod p$，并存储结果与对应的$j$（$j$从0到$m-1$，即0、1、2）：

• $j=0$: $g_1^0 ≡ 1 \pmod{p}$ → 记录$(1, 0)$
• $j=1$: $g_1^1 = 5^{125097} \mod 1000777$，用快速幂计算得：$999249$ → 记录$(999249, 1)$
• $j=2$: $g_1^2 = (999249)^2 \mod 1000777 = (-1528)^2 = 2334784 \mod 1000777 = 333230$ → 记录$(333230, 2)$

步骤3：计算大步的逆元 #

首先计算$g_1^m = g_1^3 = g_1^2 \cdot g_1 = 333230 \times 999249 \mod 1000777$，计算得：$780724$。
然后求$g_1^{m$的逆元$\text{inv}(g_1}m) \pmod{p}$，因为$p$是质数，逆元可以用费马小定理计算：$\text{inv}(g_1^m) = (g_1^m){p-2} \mod p$，或者利用$g_1^8 ≡1$的性质，$\text{inv}(g_1^3) = g_1^{8-3} = g_1^5$，最终计算得：$220053$。

步骤4：遍历大步，匹配小步表 #

初始化$\text{current} = h_1 \mod p$，然后遍历$i$从0到$m-1$（0、1、2）：

1. 当$i=0$:
   检查$\text{current}$是否在小步表中。如果是，对应的$j$就是小步表的索引，那么$x = i \cdot m + j$。
   例如，若计算得$h_1 = 333230$，则匹配到$j=2$，此时$x=0 \times3 +2=2$，验证：$g_1^2 ≡333230 ≡h_1 \pmod{p}$，成立。
2. 如果$i=0$未匹配:
   更新$\text{current} = \text{current} \times \text{inv}(g_1^m) \pmod{p}$，然后检查$i=1$，以此类推。

因为$g_1$的阶只有8，这个过程最多遍历3次就能找到解，计算量非常小。

验证解 #

找到$x$后，记得验证$g_1^x ≡h_1 \pmod{p}$，确保结果正确。比如刚才的例子$x=2$，代入计算$999249^2 mod 1000777=333230$，和$h_1$一致，说明解正确。

内容的提问来源于stack exchange，提问作者Elena