Cryptology ePrint Archive: Report 2013/074

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\F_{2^{1971}}$ and $\F_{2^{3164}}$

Faruk G\"olo\u{g}lu and Robert Granger and Gary McGuire and Jens Zumbr\"agel

Abstract: In this paper we propose a binary field variant of the Joux-Lercier medium-sized Function Field Sieve, which results not only in complexities as low as $L_{q^n}(1/3,(4/9)^{1/3})$ for computing arbitrary logarithms, but also in an heuristic {\em polynomial time} algorithm for finding the discrete logarithms of degree one and two elements when the field has a subfield of an appropriate size. To illustrate the efficiency of the method, we have successfully solved the DLP in the finite fields with $2^{1971}$ and $2^{3164}$ elements, setting a record for binary fields.

Category / Keywords: Discrete logarithm problem, function field sieve.

Publication Info: Crypto 2013 IACR version

Date: received 15 Feb 2013, last revised 7 Jun 2013

Contact author: robbiegranger at gmail com

Available format(s): PDF | BibTeX Citation

Note: Comments welcome.

Version: 20130608:001752 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]