Cryptology ePrint Archive: Report 2011/292

On Nonlinear Polynomial Selection and Geometric Progression (mod N) for Number Field Sieve

Namhun Koo and Gooc Hwa Jo and Soonhak Kwon

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 using small geometric progression (GP) (mod $N$) to construct a pair of nonlinear polynomials. We 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.

Category / Keywords: foundations / Polynomial Selection, Number Field Sieve, LLL Algorithm

Date: received 2 Jun 2011

Contact author: shkwon at skku edu

Available formats: PDF | BibTeX Citation

Version: 20110603:150917 (All versions of this report)

Discussion forum: Show discussion | Start new discussion