Index Calculus
指数计算法利用因子基与线性代数求解 Z_p^* 中离散对数，亚指数复杂度 L_p[1/2,√2]。
用途
对素数群离散对数比通用算法更快，影响 DSA/DH 参数选择。
机制
选因子基 S={小素数}。随机选 k 计算 g^k mod p，若 S-平滑则得线性关系 ∑e_i*log(s_i)≡k (mod p-1)。收集足够关系用线性代数解 log(s_i)，再求目标 log(h)。
用例
- 离散对数攻击
- 密码分析
- 数论算法
指数计算法利用因子基与线性代数求解 Z_p^* 中离散对数，亚指数复杂度 L_p[1/2,√2]。
对素数群离散对数比通用算法更快，影响 DSA/DH 参数选择。
选因子基 S={小素数}。随机选 k 计算 g^k mod p，若 S-平滑则得线性关系 ∑e_i*log(s_i)≡k (mod p-1)。收集足够关系用线性代数解 log(s_i)，再求目标 log(h)。