**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 format(s): **PDF | BibTeX Citation

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

**Short URL: **ia.cr/2011/292

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]