On nonlinear polynomial selection and geometric progression (mod $N$) for number field sieve
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
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 \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.
참고문헌 (17)
- K. Aoki, "A Kilobit special number field sieve factorization", Advances in cryptology-ASIACRYPT 2007, pp.1~12 (2007), Springer
- S. Bai, "Better Polynomials for GNFS", Mathematics of Computation
- S. Bai, "Root optimization of polynomials in the number field sieve", Math. Comp, 84(295), pp.2447~2457 (2015)
- N. Coxon, "On nonlinear polynomial selection for the number field sieve", preprint, ~ (2011)
- N. Coxon, "Montgomery’s method of polynomial selection for the number field sieve", preprent, ~ (2014)
- R. Crandall, "Prime Numbers: A Computational Perspective" (2005), Springer
- J. Gower, "Rotations and translations of number field sieve polynomials, Proceeding of Asiacrypt 2003", LNCS, 2894, pp.302~310 (2003)
- T. Kleinjung, "On polynomial selection for the general number field sieve", Math. Comp, 75, pp.2037~2047 (2006)
- T. Kleinjung, "Factorization of a 768-bit RSA modulus", Advances in cryptology-EUROCRYPTO 2010, pp.333~350 (2010), Springer
- A. K. Lenstra, "The Development of the Number Field Sieve", LNM, 1554 (1993), Springer
- A. K. Lenstra, "Factoring polynomials with rational coefficients", Math. Ann, 261(4), pp.513~534 (1982)
- P. Montgomery, "Small geometric progressions modulo n", Unpublished note of 2 pages, ~ (2005)
- B. Murphy, "Polynomial Selection for the Number Field Sieve Integer Factorisation Al-gorithm", PhD, pp.1999
- P. Nguyen, "Merkle-Hellman revisited: A cryptoanalysis of the Qu-Vanstone cryptosystem based on group factorizations", Advances in cryptology-EUROCRYPTO ’97, pp.198~212, Springer
- T. Prest, "Non-linear polynomial selection for the number field sieve", J. Symbolic Comput, 47(4), pp.401~409 (2012)
- "RSA challenge"[URL]
- R. S. Williams, "Cubic Polynomials in the Number Field Sieve", MSc, pp.2010