Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Faster individual discrete logarithms in finite fields of composite extension degree

Author: Aurore Guillevic
Journal: Math. Comp. 88 (2019), 1273-1301
MSC (2010): Primary 11T71
Published electronically: September 6, 2018
MathSciNet review: 3904147
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: Computing discrete logarithms in finite fields is a main concern in cryptography. The best algorithms in large and medium characteristic fields (e.g., $\rm {GF}(p^2)$, $\rm {GF}(p^{12})$) are the Number Field Sieve and its variants (special, high-degree, tower). The best algorithms in small characteristic finite fields (e.g., $\rm {GF}(3^{6 \cdot 509})$) are the Function Field Sieve, Joux’s algorithm, and the quasipolynomial-time algorithm. The last step of this family of algorithms is the individual logarithm computation. It computes a smooth decomposition of a given target in two phases: an initial splitting, then a descent tree. While new improvements have been made to reduce the complexity of the dominating relation collection and linear algebra steps, resulting in a smaller factor basis (database of known logarithms of small elements), the last step remains at the same level of difficulty. Indeed, we have to find a smooth decomposition of a typically large element in the finite field. This work improves the initial splitting phase and applies to any nonprime finite field. It is very efficient when the extension degree is composite. It exploits the proper subfields, resulting in a much more smooth decomposition of the target. This leads to a new trade-off between the initial splitting step and the descent step in small characteristic. Moreover it reduces the width and the height of the subsequent descent tree.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11T71

Retrieve articles in all journals with MSC (2010): 11T71

Additional Information

Aurore Guillevic
Affiliation: Inria Nancy–Grand Est, Équipe Caramba, 615 rue du jardin botanique, CS 20101, 54603 Villers-lès-Nancy Cedex, France
MR Author ID: 963265

Keywords: Finite field, discrete logarithm, number field sieve, function field sieve, individual logarithm.
Received by editor(s): July 26, 2017
Received by editor(s) in revised form: February 26, 2018
Published electronically: September 6, 2018
Article copyright: © Copyright 2018 American Mathematical Society