Index Calculus
The index calculus method solves discrete logarithms in Z_p^* using a factor base and linear algebra, with subexponential complexity L_p[1/2,√2].
Purpose
To beat generic algorithms for prime-field discrete logarithms, informing DSA/DH parameter selection.
Mechanism
Choose a factor base S={small primes}. Pick random k and compute g^k mod p; if the result is S-smooth, it yields a linear relation ∑e_i*log(s_i)≡k (mod p-1). Collect enough relations, solve for log(s_i) with linear algebra, then compute the target log(h).
Use cases
- Discrete logarithm attacks
- Cryptanalysis
- Number-theoretic algorithms