The multiple polynomial quadratic sieve
HTML articles powered by AMS MathViewer
- by Robert D. Silverman PDF
- Math. Comp. 48 (1987), 329-339 Request permission
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.References
- John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^{n}\pm 1$, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR 715603 J. Davis & D. Holdridge, Factorization Using the Quadratic Sieve, Sandia Report #SAND 83-1346, 1983. 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.
- Joseph L. Gerver, Factoring large numbers with a quadratic sieve, Math. Comp. 41 (1983), no. 163, 287–294. MR 701639, DOI 10.1090/S0025-5718-1983-0701639-4
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878 P. Montgomery, personal communication.
- Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5 C. Pomerance, personal communication.
- 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, DOI 10.1007/3-540-39757-4_{1}7
- 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
- Carl Pomerance and Samuel S. Wagstaff Jr., Implementation of the continued fraction integer factoring algorithm, Congr. Numer. 37 (1983), 99–118. MR 703581
Additional Information
- © Copyright 1987 American Mathematical Society
- Journal: Math. Comp. 48 (1987), 329-339
- MSC: Primary 11Y05
- DOI: https://doi.org/10.1090/S0025-5718-1987-0866119-8
- MathSciNet review: 866119