Factoring large numbers with a quadratic sieve
HTML articles powered by AMS MathViewer
- by Joseph L. Gerver PDF
- Math. Comp. 41 (1983), 287-294 Request permission
Abstract:
The quadratic sieve algorithm was used to factor a 47-digit number into primes. A comparison with Wagstaff’s results using the continued fraction early abort algorithm suggests that QS should be faster than CFEA when the number being factored exceeds 60 digits (plus or minus ten or more digits, depending on details of the hardware and software).References
-
J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman & S. S. Wagstaff, Jr., "Factorizations of ${b^n} \pm 1$ up to high powers." (To appear).
- E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964, DOI 10.1016/0022-314X(83)90002-1
- D. Coppersmith, Rapid multiplication of rectangular matrices, SIAM J. Comput. 11 (1982), no. 3, 467–471. MR 664714, DOI 10.1137/0211037
- John D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153, 255–260. MR 595059, DOI 10.1090/S0025-5718-1981-0595059-1
- D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. America, Buffalo, N.Y.; distributed by Prentice-Hall, Englewood Cliffs, N.J., 1969, pp. 117–151. MR 0246815
- 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, 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 C. P. Schnorr, private correspondence dated 1982 (communicated to the author by C. Pomerance). S. S. Wagstaff, Jr., private correspondence dated 1981-1982.
- Marvin C. Wunderlich, A running time analysis of Brillhart’s continued fraction factoring method, Number theory, Carbondale 1979 (Proc. Southern Illinois Conf., Southern Illinois Univ., Carbondale, Ill., 1979) Lecture Notes in Math., vol. 751, Springer, Berlin, 1979, pp. 328–342. MR 564939
Additional Information
- © Copyright 1983 American Mathematical Society
- Journal: Math. Comp. 41 (1983), 287-294
- MSC: Primary 11Y05; Secondary 11-04, 11N35
- DOI: https://doi.org/10.1090/S0025-5718-1983-0701639-4
- MathSciNet review: 701639