Index calculus algorithm (Discrete Logarithm Over Finite Fields, F q Logarithm Calculations)

Time Complexity

$O(e^{(\sqrt({2}) \sqrt(n*logn))})$

Space Complexity

$O(n+r^{2})$? bits

(See Dixon's algorithm for factoring integers; also works with an O(r)-by-O(r) sized matrix (to obtain discrete logs of primes in factor base))

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

RAM?

Year

1922

Reference

NA