On nonlinear polynomial selection and geometric progression (mod $N$) for number field sieve
Bull. Korean Math. Soc. 2016 Vol. 53, No. 1, 1-20
https://doi.org/10.4134/BKMS.2016.53.1.1
Printed January 31, 2016
Gook Hwa Cho, Namhun Koo, and Soonhak Kwon
Ewha Womans University, National Institute for Mathematical Sciences, Sungkyunkwan University
Abstract : The general number field sieve (GNFS) is asymptotically the fastest known factoring algorithm. One of the most important steps of GNFS is to select a good polynomial pair. A standard way of polynomial selection (being used in factoring RSA challenge numbers) is to select a nonlinear polynomial for algebraic sieving and a linear polynomial for rational sieving. There is another method called a nonlinear method which selects two polynomials of the same degree greater than one. In this paper, we generalize Montgomery's method \cite{Mon} using geometric progression (GP) (mod $N$) to construct a pair of nonlinear polynomials. We also introduce GP of length $d+k$ with $1\leq k\leq d-1$ and show that we can construct polynomials of degree $d$ having common root (mod $N$), where the number of such polynomials and the size of the coefficients can be precisely determined.
Keywords : polynomial selection, number field sieve, geometric progression, LLL algorithm
MSC numbers : 11Y05, 11Y16, 11B50
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd