The AMS website will be down for maintenance on May 23 between 6:00am - 8:00am EDT. For questions please contact AMS Customer Service at or (800) 321-4267 (U.S. & Canada), (401) 455-4000 (Worldwide).


Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Better polynomials for GNFS

Authors: Shi Bai, Cyril Bouvier, Alexander Kruppa and Paul Zimmermann
Journal: Math. Comp. 85 (2016), 861-873
MSC (2010): Primary 11Y05, 11Y16
Published electronically: October 19, 2015
MathSciNet review: 3434885
Full-text PDF

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 selected polynomials can be modelled in terms of size and root properties. We propose a new kind of polynomial for GNFS: with a new degree of freedom, we further improve the size property. We demonstrate the efficiency of our algorithm by exhibiting a better polynomial than the one used for the factorization of RSA-768 and a polynomial for RSA-1024 that outperforms the best published one.

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: ENS de Lyon, Laboratoire LIP, (Université de Lyon, CNRS, ENSL, INRIA, UCBL), 69007 Lyon, France

Cyril Bouvier
Affiliation: INRIA Nancy - Grand Est, 54600 Villers-lès-Nancy, France

Alexander Kruppa
Affiliation: INRIA Nancy - Grand Est, 54600 Villers-lès-Nancy, France

Paul Zimmermann
Affiliation: INRIA Nancy - Grand Est, 54600 Villers-lès-Nancy, France

Received by editor(s): June 18, 2013
Received by editor(s) in revised form: September 16, 2014
Published electronically: October 19, 2015
Additional Notes: The first author was supported in part by the ERC Starting Grant ERC-2013-StG-335086-LATTAC
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society