Non-linear polynomial selection for the number field sieve
type: Item
instance of: scholarly article
title: Non-linear polynomial selection for the number field sieve
zbMATH Open document ID: 1278.11107
author: Thomas Prest
author: Paul Zimmermann
published in: Journal of Symbolic Computation
publication date: 2012-05-04T00:00:00Z
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 6030304
zbMATH Keywords: integer factorization
zbMATH Keywords: number field sieve
zbMATH Keywords: polynomial selection
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: j.jsc.2011.09.004
OpenAlex ID: W2022432349
cites work: An Implementation of the Number Field Sieve
cites work: LLL: A Tool for Effective Diophantine Approximation
cites work: On polynomial selection for the general number field sieve
cites work: Factorization of a 768-Bit RSA Modulus
cites work: Factoring polynomials with rational coefficients
cites work: The LLL algorithm. Survey and applications
cites work: Q4406533
DOI: 10.1016/J.JSC.2011.09.004
Recommended article: On nonlinear polynomial selection and geometric progression (mod \(N\)) for number field sieve
Recommended article: Montgomery's method of polynomial selection for the number field sieve
Recommended article: Better polynomials for GNFS
Recommended article: Polynomial Selection for the Number Field Sieve
Recommended article: On polynomial selection for the general number field sieve
Recommended article: Square Root Algorithms for the Number Field Sieve
Recommended article: Root optimization of polynomials in the number field sieve
Recommended article: Q3840157
Recommended article: Q4375601
Recommended article: Q3838139
review text: The Number Field Sieve (see [\textit{A. K. Lenstra} and \textit{H. W. Lenstra jun.} (eds.), The development of the number field sieve. Lecture Notes in Mathematics. 1554. Berlin: Springer-Verlag (1993; Zbl 0777.00017)]) is the best method today to factor a large integer \(N\). A first step is to find two polynomials \(f,g\in \mathbb{Z}[X]\) sharing a common root modulo \(N\)\, or equivalently with resultant \(\text{Res}(f,g)\) a (small) multiple of \(N\) (polynomial selection).NEWLINENEWLINEUsually one takes \(g\) to be a linear polynomial and as \(f\) a polynomial of (small) degree \(d>1\). P. L. Montgomery (see \textit{M. Elkenbracht-Huizing} [Exp. Math. 5, No. 3, 231--253 (1996; Zbl 0869.11101)]) proposed a method producing polynomials \(f,g\) of degree two and recently \textit{R. S. Williams} [M. Sc. Thesis, Texas Tech. Univ. (1910)] gave an algorithm to select \(f,g\) with degree \(d=3\). The present paper generalizes Montgomery's method allowing to find polynomials of (the same) degree \(d\) for any \(d\).NEWLINENEWLINENEWLINESection 1 reminds notations and basic facts about lattices and resultants and Section 2 summarizes the state of the art in polynomial selection, describing the Montgomery and Williams algorithms. Section 3 describes the proposed method giving details of the algorithm in the case \(d=3\). In this last case the authors conclude that their method improves Williams' algorithm because ``it finds two polynomials with resultant \(O(N^{5/4})\) instead of \(O(N^{4/3})\)''. Finally Section 4 discusses the open question of how to produce polynomials \(f,g\) of different degrees, in particular \(d\) and \(d-1\).
description: scientific article; zbMATH DE number 6030304