Cryptology ePrint Archive: Report 2014/300

On the Powers of 2

Robert Granger and Thorsten Kleinjung and Jens Zumbrägel

Abstract: In 2013 the function field sieve algorithm for computing discrete logarithms in finite fields of small characteristic underwent a series of dramatic improvements, culminating in the first heuristic quasi-polynomial time algorithm, due to Barbulescu, Gaudry, Joux and Thomé. In this article we present an alternative descent method which is built entirely from the on-the-fly degree two elimination method of G\"oloğlu, Granger, McGuire and Zumbr\"agel. This also results in a heuristic quasi-polynomial time algorithm, for which the descent does not require any relation gathering or linear algebra eliminations and interestingly, does not require any smoothness assumptions about non-uniformly distributed polynomials. These properties make the new descent method readily applicable at currently viable bitlengths and better suited to theoretical analysis.

Category / Keywords: public-key cryptography / discrete logarithm problem, finite fields, quasi-polynomial time algorithm

Date: received 29 Apr 2014

Contact author: thorsten kleinjung at epfl ch

Available format(s): PDF | BibTeX Citation

Version: 20140430:121216 (All versions of this report)

Short URL: ia.cr/2014/300

Discussion forum: Show discussion | Start new discussion