Discrete Logarithm Over Finite Fields

Description

Let $F_{p^n}$ denote the finite field of $p^n$ elements, where $p$ is a prime. Let $x$ be a generator for the multiplicative group of $F_{p^n}$. The discrete logarithm problem over $F_{p^n}$ is to compute, for any given nonzero $h \in F_{p^n}$, the least nonnegative integer $e$ such that $x^e=h$. In this context we shall write $e=\log_x h$.

Parameters

$n$: number of digits/bits in the order of the finite group

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Trial Multiplication	1940	$O({2}^n)$	$O({1})$	Exact	Deterministic
Baby-step Giant-step	1971	$O({2}^{\sqrt{n}})$	$O({2}^{\sqrt{n}})$	Exact	Deterministic	Time
Function Field Sieve (FFS)	1999	$O({2}^n)$	$O(n^{2/3})$?	Exact	Deterministic	Time
Index calculus algorithm	1922	$O(e^{(\sqrt({2}) \sqrt(n*logn))})$	$O(n+r^{2})$?	Exact	Deterministic
Number Field Sieve (NFS)	1990	$O({2}^n)$	$O(n^{2/3})$	Exact	Deterministic	Time & Space
Pohlig-Hellman	1978	$O({2}^{\sqrt{n}})$, only for primes; does much better for composites	$O({2}^{\sqrt{n}})$ (though only for primes)	Exact	Deterministic	Time
Pollard's rho algorithm	1978	$O({2}^{(n/{2})})$	$O({1})$	Exact	Deterministic	Time
Pollard's kangaroo algorithm	1978	$O({2}^n)$	$O({1})$	Exact	Deterministic	Time

Time Complexity Graph