Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Root optimization of polynomials in the number field sieve

Authors: Shi Bai, Richard P. Brent and Emmanuel Thomé
Journal: Math. Comp. 84 (2015), 2447-2457
MSC (2010): Primary 11Y05, 11Y16
Published electronically: February 11, 2015
MathSciNet review: 3356034
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the chosen polynomials in polynomial selection can be modelled in terms of size and root properties. In this paper, we describe some algorithms for selecting polynomials with very good root properties.

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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y05, 11Y16

Retrieve articles in all journals with MSC (2010): 11Y05, 11Y16

Additional Information

Shi Bai
Affiliation: Department of Mathematics, University of Auckland, Auckland, New Zealand.

Richard P. Brent
Affiliation: Mathematical Sciences Institute, Australian National University, Australia.

Emmanuel Thomé
Affiliation: INRIA Nancy, Villers-lès-Nancy, France.

Received by editor(s): June 14, 2013
Received by editor(s) in revised form: October 30, 2013, and December 7, 2013
Published electronically: February 11, 2015
Article copyright: © Copyright 2015 American Mathematical Society