University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Indiscreet logarithms in finite fields of small characteristic

Granger, Robert, Kleinjung, Thorsten and Zumbrägel, Jens (2018) Indiscreet logarithms in finite fields of small characteristic Advances in Mathematics of Communications, 12 (2). pp. 263-286.

[img]
Preview
Text
RG_survey-9.pdf - Accepted version Manuscript

Download (352kB) | Preview

Abstract

Recently, several striking advances have taken place regarding the discrete logarithm problem (DLP) in finite fields of small characteristic, despite progress having remained essentially static for nearly thirty years, with the best known algorithms being of subexponential complexity. In this expository article we describe the key insights and constructions which culminated in two independent quasi-polynomial algorithms. To put these developments into both a historical and a mathematical context, as well as to provide a comparison with the cases of so-called large and medium characteristic fields, we give an overview of the state-of-the-art algorithms for computing discrete logarithms in all finite fields. Our presentation aims to guide the reader through the algorithms and their complexity analyses ab initio.

Item Type: Article
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
NameEmailORCID
Granger, Robertr.granger@surrey.ac.uk
Kleinjung, Thorsten
Zumbrägel, Jens
Date : May 2018
DOI : 10.3934/amc.2018017
Copyright Disclaimer : Copyright © 2019 American Institute of Mathematical Sciences
Uncontrolled Keywords : Discrete logarithm problem; Finite fields; Number field sieve; Function field sieve; Quasi-polynomial algorithms
Depositing User : Clive Harris
Date Deposited : 06 Feb 2019 13:15
Last Modified : 31 May 2019 02:08
URI: http://epubs.surrey.ac.uk/id/eprint/850380

Actions (login required)

View Item View Item

Downloads

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