Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Email: Antoine.Joux@m4x.org

Reynald Lercier
Affiliation: CELAR, Route de Laillé, F-35998 Rennes Armées, France
Email: lercier@celar.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-02-01482-5
PII: S 0025-5718(02)01482-5
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