Welcome to the resource topic for
**2011/292**

**Title:**

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

**Authors:**
Namhun Koo, Gooc Hwa Jo, 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.

**ePrint:**
https://eprint.iacr.org/2011/292

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .