Hacker News Reader

> 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.

View on HN

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...

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

Reply on news.ycombinator.com