[pbsd]

You're not wrong. The current state of the art puts the precomputation step at complexity L_n(1/3, 1.923)§, and additional individual discrete logs at L_n(1/3, 1.232). So individual logarithms are still subexponential and nothing to scoff at, but they do become easier, yes.

Ignoring constant factors, for a 1536-bit prime this would mean cost ~2^102 for the initial precomputation, and ~2^66 for each individual log.

§ L_n(a, c) is the usual exp(c(1 + o(1)) (log n)^a (loglog n)^(1-a)).

[bhitov]

> The current state of the art puts the precomputation step at complexity L_n(1/3, 1.923)§, and additional individual discrete logs at L_n(1/3, 1.232).

Could you cite that? Not skeptical, just interested.

[pbsd]

Razvan Barbulescu's PhD thesis [1]. Note that the best asymptotic complexities are a little different: the 'best' is really L_n(1/3, 1.902), but that variant is hopeless in practice (it would require truly gigantic inputs for it to pay off). Similarly, there is a "discrete logarithm factory" method, based on Coppersmith's factorization factory, but that also has very large initial costs that make it not very attractive in practice.

[1] http://tel.archives-ouvertes.fr/docs/00/92/52/28/PDF/these_a...

[bhitov]

Much appreciated =). I looked for references after reading the parent discussions and xnyhps's blog post but was unsuccessful.