The computational complexity of discrete log

Question

I am trying to find out what the asymptotic computational complexity, in terms of big $O()$ notation, is for discrete log. Specifically, consider an element of the field $x \in \mathbb{F}_{q}$, what is:

• The worst case rigorously provable complexity of computing the discrete log of $x$ if a) $q$ is a prime or b) if $q = 2^k$?
• The best known heuristic complexity of computing the discrete log of $x$ if a) $q$ is a prime or b) if $q = 2^k$?

This looks like a standard question and I have searched the web but I can't find clear answers to these questions (including on the wiki).

As a side note, are there particular fields for which discrete logs are easier than others?

---

An example of information from which I am not able to glean the answers to my questions is the paper The Past, evolving Present and Future of Discrete Logarithm. Section 4 lists a number of relevant methods but no clear statement of their asymptotic complexity in terms of the number of bits needed to represent the field element and $q$ (or $k$) that I can find. It's possible I am just not interpreting the paper well of course.

Answer 1

The paper you mention actually does contain most of the answers at least as far as “heuristic complexity” is concerned (newer results improve the complexity bounds given in that paper in some parameter ranges, but not the ranges you are asking about). Note that the complexity of the discrete logarithm problem is usually given for a random $x$ (with respect to an arbitrary generator of $\mathbb{F}_q^*$), so the bit length of $x$ doesn't really come into play.

So the best known algorithm for discrete logarithms in $\mathbb{F}_q^*$ when $q$ is a random-looking prime is the general number field sieve (GNFS), which has a heuristic complexity of $L_q[1/3,\sqrt[3]{64/9}]$, where $L_q[\alpha,c]$ is a short-hand notation for $\exp\big((c+o(1))(\log q)^\alpha(\log\log q)^{1-\alpha}\big)$.

Still in the prime case, when $q$ has a special form (which roughly means that it can be expressed as the value of a polynomial with small coefficients at a small integer: think e.g. of a Mersenne prime), one can use the special number field sieve (SNFS) instead, and complexity drops down to $L_q[1/3,\sqrt[3]{32/9}]$ (so one can solve the problem for $q$ of roughly twice the bit size as for SNFS).

As for the case of $q=2^k$, the best asymptotic complexity is provided by Barbulescu et al.'s version of the function field sieve (FFS), which in that case runs in heuristic quasipolynomial time $2^{O((\log k)^2)}$.

All of these complexity estimates depend on heuristic assumptions of the form “such and such family of integers/polynomials contains roughly as many smooth elements as random integers/polynomials of the same size”, so making them entirely rigorous is probably hopeless. In practice, though, they work as advertised (extensive experiments support the estimates in most cases).

Oh, and as a final note, you can probably deduce from the above that the answer to the question of whether the discrete log problem is easier in some fields than others is yes. Basically, for a field $\mathbb{F}_{p^k}$ with $p$ prime, the complexity will depend on the relative sizes of $p$ and $k$ (this is the distinction between the small prime, medium prime and large prime cases of the discrete log discussed in the paper of Joux et al.), and to a lesser extent on whether $p$ has a special form in the sense alluded to above.