Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method

Authors: Antoine Joux and Reynald Lercier
Journal: Math. Comp. 72 (2003), 953-967
MSC (2000): Primary 11T99; Secondary 11Y05
Published electronically: November 4, 2002
MathSciNet review: 1954978
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we describe many improvements to the number field sieve. Our main contribution consists of a new way to compute individual logarithms with the number field sieve without solving a very large linear system for each logarithm. We show that, with these improvements, the number field sieve outperforms the gaussian integer method in the hundred digit range. We also illustrate our results by successfully computing discrete logarithms with GNFS in a large prime field.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11T99, 11Y05

Retrieve articles in all journals with MSC (2000): 11T99, 11Y05

Additional Information

Antoine Joux
Affiliation: DCSSI, 18 rue du Dr. Zamenhoff, F-92131 Issy-les-Moulineaux, France
MR Author ID: 316495

Reynald Lercier
Affiliation: CELAR, Route de Laillé, F-35998 Rennes Armées, France
MR Author ID: 602270
ORCID: 0000-0002-0531-8945

Received by editor(s): July 27, 1999
Received by editor(s) in revised form: October 18, 2000
Published electronically: November 4, 2002
Article copyright: © Copyright 2002 American Mathematical Society