Show simple item record

Computation of a 30 750-Bit Binary Field Discrete Logarithm

hal.structure.identifierUniversity of Surrey [UNIS]
dc.contributor.authorGRANGER, Robert
hal.structure.identifierEcole Polytechnique Fédérale de Lausanne [EPFL]
dc.contributor.authorKLEINJUNG, Thorsten
hal.structure.identifierEcole Polytechnique Fédérale de Lausanne [EPFL]
dc.contributor.authorLENSTRA, Arjen
hal.structure.identifierLithe and fast algorithmic number theory [LFANT]
hal.structure.identifierCentre National de la Recherche Scientifique [CNRS]
dc.contributor.authorWESOLOWSKI, Benjamin
hal.structure.identifierUniversität Passau [Passau]
dc.contributor.authorZUMBRÄGEL, Jens
dc.date.accessioned2024-04-04T02:49:38Z
dc.date.available2024-04-04T02:49:38Z
dc.date.issued2021
dc.identifier.issn0025-5718
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191839
dc.description.abstractEnThis paper reports on the computation of a discrete logarithm in the finite field $\mathbb F_{2^30750}$, breaking by a large margin the previous record, which was set in January 2014 by a computation in $\mathbb F_{2^30750}$. The present computation made essential use of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbrägel, and is the first large-scale experiment to truly test and successfully demonstrate its potential when applied recursively, which is when it leads to the stated complexity. It required the equivalent of about 2900 core years on a single core of an Intel Xeon Ivy Bridge processor running at 2.6 GHz, which is comparable to the approximately 3100 core years expended for the discrete logarithm record for prime fields, set in a field of bit-length 795, and demonstrates just how much easier the problem is for this level of computational effort. In order to make the computation feasible we introduced several innovative techniques for the elimination of small degree irreducible elements, which meant that we avoided performing any costly Gröbner basis computations, in contrast to all previous records since early 2013. While such computations are crucial to the $L(1/4 + o(1))$ complexity algorithms, they were simply too slow for our purposes. Finally, this computation should serve as a serious deterrent to cryptographers who are still proposing to rely on the discrete logarithm security of such finite fields in applications, despite the existence of two quasi-polynomial algorithms and the prospect of even faster algorithms being developed.
dc.language.isoen
dc.publisherAmerican Mathematical Society
dc.subject.enDiscrete logarithm problem
dc.subject.enFinite fields
dc.subject.enBinary fields
dc.subject.enQuasi-polynomial algorithm
dc.title.enComputation of a 30 750-Bit Binary Field Discrete Logarithm
dc.typeArticle de revue
dc.identifier.doi10.1090/mcom/3669
dc.subject.halMathématiques [math]/Théorie des nombres [math.NT]
dc.subject.halInformatique [cs]/Cryptographie et sécurité [cs.CR]
bordeaux.journalMathematics of Computation
bordeaux.volume90
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue332
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-02945361
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02945361v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Mathematics%20of%20Computation&rft.date=2021&rft.volume=90&rft.issue=332&rft.eissn=0025-5718&rft.issn=0025-5718&rft.au=GRANGER,%20Robert&KLEINJUNG,%20Thorsten&LENSTRA,%20Arjen&WESOLOWSKI,%20Benjamin&ZUMBR%C3%84GEL,%20Jens&rft.genre=article


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record