Factoring large numbers with a quadratic sieve
Author: Joseph L. Gerver
Journal: Math. Comp. 41 (1983), 287-294
MSC: Primary 11Y05; Secondary 11-04, 11N35
MathSciNet review: 701639
Full-text PDF Free Access
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).
-  J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman & S. S. Wagstaff, Jr., "Factorizations of 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, https://doi.org/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, https://doi.org/10.1137/0211037
-  John D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153, 255–260. MR 595059, https://doi.org/10.1090/S0025-5718-1981-0595059-1
-  D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. Amer. (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 𝐹₇, Math. Comp. 29 (1975), 183–205. MR 371800, https://doi.org/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
- J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman & S. S. Wagstaff, Jr., "Factorizations of up to high powers." (To appear).
- E. R. Canfield, P. Erdos & C. Pomerance, "On a problem of Oppenheim concerning 'Factorisatio Numerorum'," J. Number Theory. (To appear.) MR 712964 (85j:11012)
- D. Coppersmith & S. Winograd, "On the asymptotic complexity of matrix multiplication," SIAM J. Comput. (To appear.) MR 664715 (83j:68047b)
- J. D. Dixon, "Asymptotically fast factorization of integers," Math. Comp., v. 36, 1981, pp. 255-260. MR 595059 (82a:10010)
- D. H. Lehmer, "Computer technology applied to the theory of numbers," in Studies in Number Theory (W.J. LeVeque, ed.), Math. Assoc. Amer., 1969,pp. 117-151. MR 0246815 (40:84)
- M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of ," Math. Comp., v. 29, 1975, pp. 183-205. MR 0371800 (51:8017)
- C. Pomerance, "Analysis and comparison of some factoring algorithms," in Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centrum, Amsterdam. (To appear.) MR 700260 (84i:10005)
- C. P. Schnorr, private correspondence dated 1982 (communicated to the author by C. Pomerance).
- S. S. Wagstaff, Jr., private correspondence dated 1981-1982.
- M. C. Wunderlich, "A running time analysis of Brillhart's continued fraction factoring method," in Number Theory Carbondale 1979 (M. B. Nathanson, ed.), Lecture Notes in Math., Vol. 751, Springer-Verlag, 1979, pp. 328-342. MR 564939 (81f:10011)