Discrete Logarithm Over Finite Fields

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 7 of 7 algorithms


Function Field Sieve (FFS)	1999	$O(\exp((1+o(1))(32n/9)^{1/3}(\log n)^{2/3}))$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(n^{2/3})$
Number Field Sieve (NFS)	1990	$O(\exp((1+o(1))(64n/9)^{1/3}(\log n)^{2/3}))$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(n^{2/3})$
Pohlig-Hellman	1978	$O(2^{\sqrt{n}})$	$O(2^{\sqrt{n}})$ (though only for primes)
Pollard's rho algorithm	1978	$O(2^{n/2})$	$O(1)$
Pollard's kangaroo algorithm	1978	$O(2^n)$	$O(1)$
Baby-step Giant-step	1971	$O(2^{\sqrt{n}})$	$O(2^{\sqrt{n}})$
Trial Multiplication	1940	$O(2^n)$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms