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öloğlu; Robert Granger; Gary McGuire; Jens Zumbrägel

Paper 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öloğlu, Robert Granger, Gary McGuire, and Jens Zumbrägel

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.

Note: Comments welcome.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Crypto 2013 IACR version
Keywords: Discrete logarithm problem function field sieve.
Contact author(s): robbiegranger @ gmail com
History: 2013-06-08: last of 2 revisions; 2013-02-20: received; See all versions
Short URL: https://ia.cr/2013/074
License: CC BY

BibTeX

@misc{cryptoeprint:2013/074,
      author = {Faruk Göloğlu and Robert Granger and Gary McGuire and Jens Zumbrägel},
      title = {On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\F_{2^{1971}}$ and $\F_{2^{3164}}$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/074},
      year = {2013},
      url = {https://eprint.iacr.org/2013/074}
}

Paper 2013/074

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in \F21971 and \F23164

Abstract

Metadata

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