HackerPapers

arXiv:1306.4244cs.CR

A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic

Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thomé

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

In the present work, we present a new discrete logarithm algorithm, in the same vein as in recent works by Joux, using an asymptotically more efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the discrete logarithm problem in finite field of small characteristic. By quasi-polynomial, we mean a complexity of type $n^{O(\log n)}$ where $n$ is the bit-size of the cardinality of the finite field. Such a complexity is smaller than any $L(\varepsilon)$ for $ε>0$. It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to $L(1/4+o(1))$.

arXiv comments
Journal reference
DOI
Subjects
cs.CRCryptography and Security math.NTNumber Theory

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from May 2014 to May 2014. Found in 1 HN submission from May 2014 to May 2014. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Une percée en mathématique rend caduques des procédures de chiffrement 1 comment

    • Here is the paper: http://arxiv.org/abs/1306.4244 ("A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic")

      AlDante2View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.