离散对数问题

离散对数问题是原根给出的"模幂的逆问题"：给定原根 $g$ 与 $a$，求 $x$ 使 $g^x\equiv a\pmod p$。幂运算容易、求对数困难，这一不对称性与大数分解共同支撑 Diffie–Hellman、ElGamal 等公钥密码的安全性。

问题表述

设 $p$ 为素数，$g$ 为模 $p$ 的原根。对任意 $p\nmid a$，存在唯一 $x\in\{1,\dots,p-1\}$ 使 $g^x\equiv a\pmod p$，记 $x=\log_g a$（即原根中的 $\mathrm{ind}_g a$）。

大步小步算法（BSGS）

取 $m=\lceil\sqrt p\rceil$，把 $x=im+j$ 写成 $0\le i<m$、$0\le j<m$。小步：预计算 $g^j$（$j=0,\dots,m-1$）存入查找表；大步：依次检验 $a(g^{-m})^i$ 是否等于某个 $g^j$，命中即得 $x=im+j$。时间与空间均为 $O(\sqrt p)$。

其他算法

• Pollard ρ 离散对数：$O(\sqrt p)$ 时间、$O(1)$ 空间
• 指数积分法（index calculus）：对 $\mathbb{F}_p^\times$ 亚指数时间，但对椭圆曲线群不适用（见椭圆曲线）

示例

解 $2^x\equiv7\pmod{29}$（$2$ 是模 $29$ 的原根，$2^{14}\equiv-1$）。$m=\lceil\sqrt{29}\rceil=6$：

• 小步：$2^j\equiv1,2,4,8,16,3$（$j=0,\dots,5$）
• $2^{-6}\equiv5\pmod{29}$，大步：$7\cdot5^0=7$，$7\cdot5\equiv6$，$7\cdot5^2\equiv1=2^0$ → $i=2$，$j=0$，$x=12$
  验证：$2^{12}=4096=141\cdot29+7\equiv7\pmod{29}$。

应用

离散对数问题与大数分解同属经典困难问题；Shor算法可在量子计算机上多项式时间求解它，故 ECC、Diffie–Hellman 均面临后量子威胁。