The multiple polynomial quadratic sieve

Silverman, Robert D.

doi:10.1090/S0025-5718-1987-0866119-8

The multiple polynomial quadratic sieve

Author: Robert D. Silverman
Journal: Math. Comp. 48 (1987), 329-339
MSC: Primary 11Y05
DOI: https://doi.org/10.1090/S0025-5718-1987-0866119-8
MathSciNet review: 866119
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A modification, due to Peter Montgomery, of Pomerance's Quadratic Sieve for factoring large integers is discussed along with its implementation. Using it, allows factorization with over an order of magnitude less sieving than the basic algorithm. It enables one to factor numbers in the 60-digit range in about a day, using a large minicomputer. The algorithm has features which make it well adapted to parallel implementation.

[1] John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of 𝑏ⁿ±1, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. 𝑏=2,3,5,6,7,10,11,12 up to high powers. MR 715603
[2] J. Davis & D. Holdridge, Factorization Using the Quadratic Sieve, Sandia Report #SAND 83-1346, 1983.
[3] J. Davis & D. Holdridge, "Status report on factoring," Advances in Cryptology (T. Beth, N. Cot, and I. Ingemarrson, eds.), Lecture Notes in Comput. Sci., vol. 209, Springer-Verlag, Berlin and New York, 1985, pp. 183-215.
[4] Joseph L. Gerver, Factoring large numbers with a quadratic sieve, Math. Comp. 41 (1983), no. 163, 287–294. MR 701639, https://doi.org/10.1090/S0025-5718-1983-0701639-4
[5] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
[6] P. Montgomery, personal communication.
[7] Michael A. Morrison and John Brillhart, A method of factoring and the factorization of 𝐹₇, Math. Comp. 29 (1975), 183–205. MR 371800, https://doi.org/10.1090/S0025-5718-1975-0371800-5
[8] C. Pomerance, personal communication.
[9] Carl Pomerance, The quadratic sieve factoring algorithm, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 169–182. MR 825590, https://doi.org/10.1007/3-540-39757-4_17
[10] C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260
[11] Carl Pomerance and Samuel S. Wagstaff Jr., Implementation of the continued fraction integer factoring algorithm, Congr. Numer. 37 (1983), 99–118. MR 703581