4 ms·
> 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 y
by bhitov 13y ago
> 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 13y agoRazvan 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_avec_resume.pdf http://tel.archives-ouvertes.fr/docs/00/92/52/28/PDF/these_a...
- bhitov 13y agoMuch appreciated =). I looked for references after reading the parent discussions and xnyhps's blog post but was unsuccessful.