Paper 2013/306

Solving a $6120$-bit DLP on a Desktop Computer

Faruk Golouglu, Robert Granger, Gary McGuire, and Jens Zumbragel

Abstract

In this paper we show how some recent ideas regarding the discrete logarithm problem (DLP) in finite fields of small characteristic may be applied to compute logarithms in some very large fields extremely efficiently. By combining the polynomial time relation generation from the authors' CRYPTO 2013 paper, an improved degree two elimination technique, and an analogue of Joux's recent small-degree elimination method, we solved a DLP in the record-sized finite field of $2^{6120}$ elements, using just a single core-month. Relative to the previous record set by Joux in the field of $2^{4080}$ elements, this represents a $50\%$ increase in the bitlength, using just $5\%$ of the core-hours. We also show that for the fields considered, the parameters for Joux's $L_Q(1/4 + o(1))$ algorithm may be optimised to produce an $L_Q(1/4)$ algorithm.

Note: Final published version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. T. Lange, K. Lauter, and P. Lisonek (Eds.): SAC 2013, LNCS 8282, pp. 136–152, 2014
DOI
10.1007/978-3-662-43414-7_7
Keywords
Discrete logarithm problembinary finite fields
Contact author(s)
dr robert granger @ gmail com
History
2019-01-25: last of 4 revisions
2013-05-25: received
See all versions
Short URL
https://ia.cr/2013/306
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/306,
      author = {Faruk Golouglu and Robert Granger and Gary McGuire and Jens Zumbragel},
      title = {Solving a $6120$-bit {DLP} on a Desktop Computer},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/306},
      year = {2013},
      doi = {10.1007/978-3-662-43414-7_7},
      url = {https://eprint.iacr.org/2013/306}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.