Bull. Korean Math. Soc. 2016; 53(1): 1-20
Printed January 31, 2016
https://doi.org/10.4134/BKMS.2016.53.1.1
Copyright © The Korean Mathematical Society.
Gook Hwa Cho, Namhun Koo, and Soonhak Kwon
Ewha Womans University, National Institute for Mathematical Sciences, Sungkyunkwan University
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
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd