Paper 2011/292

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

Namhun Koo, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Polynomial SelectionNumber Field SieveLLL Algorithm
Contact author(s)
shkwon @ skku edu
History
2011-06-03: received
Short URL
https://ia.cr/2011/292
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/292,
      author = {Namhun Koo and Gooc Hwa Jo and Soonhak Kwon},
      title = {On Nonlinear Polynomial Selection and Geometric Progression (mod N) for Number Field Sieve},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/292},
      year = {2011},
      url = {https://eprint.iacr.org/2011/292}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.