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

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.

Lange, Tanja
Lauter, Kristin
Lisoněk, Petr
Published in:
Selected Areas in Cryptography -- SAC 2013, 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, 136-152
Presented at:
Selected Areas in Cryptography -- SAC 2013, Burnaby, BC, Canada, August 14-16, 2013
Springer Berlin Heidelberg

 Record created 2016-01-19, last modified 2019-03-17

External link:
Download fulltext
Rate this document:

Rate this document:
(Not yet reviewed)