×

Montgomery’s method of polynomial selection for the number field sieve. (English) Zbl 1357.11121

Summary: The number field sieve is the most efficient known algorithm for factoring large integers that are free of small prime factors. For the polynomial selection stage of the algorithm, Montgomery proposed a method of generating polynomials which relies on the construction of small modular geometric progressions. Montgomery’s method is analysed in this paper and the existence of suitable geometric progressions is considered.

MSC:

11Y05 Factorization
11Y16 Number-theoretic algorithms; complexity

Software:

CADO-NFS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aitken, A. C., Determinants and Matrices (1944), Oliver and Boyd: Oliver and Boyd Edinburgh · Zbl 0060.03106
[3] Bai, Shi; Brent, Richard P.; Thomé, Emmanuel, Root optimization of polynomials in the number field sieve, Math. Comp., 84, 295, 2447-2457 (2015) · Zbl 1378.11104
[4] Bai, Shi; Thomé, Emmanuel; Zimmermann, Paul, Factorisation of RSA-704 with CADO-NFS (2012), cryptology ePrint archive, Report 2012/369
[5] Brualdi, Richard A.; Schneider, Hans, Determinantal identities: Gauss, Schur, Cauchy, Sylvester, Kronecker, Jacobi, Binet, Laplace, Muir, and Cayley, Linear Algebra Appl., 52/53, 769-791 (1983) · Zbl 0533.15007
[6] Canfield, E. R.; Erdős, Paul; Pomerance, Carl, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory, 17, 1, 1-28 (1983) · Zbl 0513.10043
[7] Cohen, Henri, A Course in Computational Algebraic Number Theory, Grad. Texts in Math., vol. 138 (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0786.11071
[8] Coxon, Nicholas, On nonlinear polynomial selection for the number field sieve (2011), arXiv e-Print archive · Zbl 1357.11121
[9] Crandall, Richard; Pomerance, Carl, Prime Numbers: A Computational Perspective (2005), Springer: Springer New York · Zbl 1088.11001
[10] El Kahoui, M’hammed, An elementary approach to subresultants theory, J. Symbolic Comput., 35, 3, 281-292 (2003) · Zbl 1054.13014
[11] Fischer, E., Über den hadamardschen determinantensatz, Arch. Math. Phys., 13, 3, 32-40 (1908) · JFM 39.0216.02
[12] Gomez, Domingo; Gutierrez, Jaime; Ibeas, Álvar; Sevilla, David, Common factors of resultants modulo \(p\), Bull. Aust. Math. Soc., 79, 2, 299-302 (2009) · Zbl 1161.13001
[13] Hadamard, Jacques, Résolution d’une question relative aux déterminants, Bull. Sci. Math., 17, 240-246 (1893) · JFM 25.0221.02
[14] Heinig, Georg; Rost, Karla, Introduction to Bezoutians, (Bini, D. A.; Mehrmann, V.; Olshevsky, V.; Tyrtsyhnikov, E.; van Barel, M., Numerical Methods for Structured Matrices and Applications. Numerical Methods for Structured Matrices and Applications, Oper. Theory Adv. Appl., vol. 199 (2010), Birkhäuser Verlag: Birkhäuser Verlag Basel), 25-118 · Zbl 1203.15020
[15] Kleinjung, Thorsten, On polynomial selection for the general number field sieve, Math. Comp., 75, 256, 2037-2047 (2006) · Zbl 1183.11079
[16] Kleinjung, Thorsten, Polynomial selection, Slides presented at the CADO workshop on integer factorization (2008), Nancy, France
[17] Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thomé, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alexander; Montgomery, Peter L.; Arne Osvik, Dag; te Riele, Herman; Timofeev, Andrey; Zimmermann, Paul, Factorization of a 768-bit RSA modulus, (Rabin, Tal, Advances in Cryptology-CRYPTO 2010. Advances in Cryptology-CRYPTO 2010, Lecture Notes in Comput. Sci., vol. 6223 (2010), Springer: Springer Berlin), 333-350 · Zbl 1196.11167
[18] Koo, Namhun; Hwa Jo, Gooc; Kwon, Soonhak, On nonlinear polynomial selection and geometric progression (mod N) for number field sieve (2011), cryptology ePrint archive, Report 2011/292 · Zbl 1371.11156
[19] Lander, F. I., The Bezoutian and the inversion of Hankel and Toeplitz matrices, Mat. Issled., 9, 2(32), 69-87 (1974), 249-250 · Zbl 0331.15017
[20] (Lenstra, A. K.; Lenstra, H. W., The Development of the Number Field Sieve. The Development of the Number Field Sieve, Lecture Notes in Math., vol. 1554 (1993), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0777.00017
[21] Mishra, Bhubaneswar, Algorithmic Algebra (1993), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. New York · Zbl 0804.13009
[22] Montgomery, Peter L., Small geometric progressions modulo \(n (1993)\), unpublished note of 2 pages, revised 1995 and 2005
[23] Montgomery, Peter L., Searching for higher-degree polynomials for the general number field sieve (2006), power-point presentation, 34 pages
[24] Murphy, Brian A., Modelling the yield of number field sieve polynomials, (Buhler, Joe P., Algorithmic Number Theory. Algorithmic Number Theory, Lecture Notes in Comput. Sci., vol. 1423 (1998), Springer: Springer Berlin), 137-150 · Zbl 0985.11064
[25] Murphy, Brian A., Polynomial selection for the number field sieve integer factorisation algorithm (1999), Australian National University, Ph.D. thesis
[26] (Nguyen, Phong Q.; Vallée, Brigitte, The LLL Algorithm: Survey and Applications. The LLL Algorithm: Survey and Applications, Inf. Secur. Cryptography (2010), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1179.11003
[27] Prest, Thomas; Zimmermann, Paul, Non-linear polynomial selection for the number field sieve, J. Symbolic Comput., 47, 4, 401-409 (2012) · Zbl 1278.11107
[28] Rivest, R. L.; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21, 2, 120-126 (1978) · Zbl 0368.94005
[29] Sederberg, Tom; Goldman, Ron; Du, Hang, Implicitizing rational curves by the method of moving algebraic curves, J. Symbolic Comput., 23, 2-3, 153-175 (1997) · Zbl 0872.68193
[30] Tyrtyshnikov, Eugene, Hankel minors and Pade approximations, (Bini, D. A.; Mehrmann, V.; Olshevsky, V.; Tyrtsyhnikov, E.; van Barel, M., Numerical Methods for Structured Matrices and Applications. Numerical Methods for Structured Matrices and Applications, Oper. Theory Adv. Appl., vol. 199 (2010), Birkhäuser Verlag: Birkhäuser Verlag Basel), 431-439 · Zbl 1203.15005
[31] Williams, Ronnie S., Cubic polynomials in the number field sieve (2010), Texas Tech University, Master’s thesis
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.