University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Solving a 6120-bit DLP on a Desktop Computer

Göloğlu, Faruk, Granger, Robert, McGuire, Gary and Zumbrägel, Jens (2014) Solving a 6120-bit DLP on a Desktop Computer In: 20th International Conference on Selected Areas in Cryptography, 14-16 Aug 2013, Burnaby, BC, Canada.

RG_sac7.pdf - Accepted version Manuscript

Download (345kB) | Preview


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 26120 elements, using just a single core-month. Relative to the previous record set by Joux in the field of 24080 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 LQ(1/4 + o(1)) algorithm may be optimised to produce an LQ(1/4) algorithm.

Item Type: Conference or Workshop Item (Conference Paper)
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
Göloğlu, Faruk
McGuire, Gary
Zumbrägel, Jens
Date : 21 May 2014
DOI : 10.1007/978-3-662-43414-7_7
Copyright Disclaimer : © Springer-Verlag Berlin Heidelberg 2014
Uncontrolled Keywords : Discrete logarithm problem; Binary finite fields
Depositing User : Clive Harris
Date Deposited : 07 Feb 2019 11:49
Last Modified : 16 Apr 2019 16:31

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800