Index Calculus
指数計算法（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) を計算する。
ユースケース
- 離散対数（DLP）への攻撃
- クリプトの解読
- 数論アルゴリズム