Factoring large numbers with a quadratic sieve
Author:
Joseph L. Gerver
Journal:
Math. Comp. 41 (1983), 287294
MSC:
Primary 11Y05; Secondary 1104, 11N35
MathSciNet review:
701639
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The quadratic sieve algorithm was used to factor a 47digit 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).
 [1]
J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman & S. S. Wagstaff, Jr., "Factorizations of up to high powers." (To appear).
 [2]
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
(85j:11012), http://dx.doi.org/10.1016/0022314X(83)900021
 [3]
D.
Coppersmith and S.
Winograd, On the asymptotic complexity of matrix
multiplication, SIAM J. Comput. 11 (1982),
no. 3, 472–492. MR 664715
(83j:68047b), http://dx.doi.org/10.1137/0211038
 [4]
John
D. Dixon, Asymptotically fast factorization of
integers, Math. Comp. 36
(1981), no. 153, 255–260. MR 595059
(82a:10010), http://dx.doi.org/10.1090/S00255718198105950591
 [5]
D.
H. Lehmer, Computer technology applied to the theory of
numbers, Studies in Number Theory, Math. Assoc. Amer. (distributed by
PrenticeHall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR 0246815
(40 #84)
 [6]
Michael
A. Morrison and John
Brillhart, A method of factoring and the
factorization of 𝐹₇, Math.
Comp. 29 (1975),
183–205. Collection of articles dedicated to Derrick Henry Lehmer on
the occasion of his seventieth birthday. MR 0371800
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 [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
(84i:10005)
 [8]
C. P. Schnorr, private correspondence dated 1982 (communicated to the author by C. Pomerance).
 [9]
S. S. Wagstaff, Jr., private correspondence dated 19811982.
 [10]
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
(81f:10011)
 [1]
 J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman & S. S. Wagstaff, Jr., "Factorizations of up to high powers." (To appear).
 [2]
 E. R. Canfield, P. Erdos & C. Pomerance, "On a problem of Oppenheim concerning 'Factorisatio Numerorum'," J. Number Theory. (To appear.) MR 712964 (85j:11012)
 [3]
 D. Coppersmith & S. Winograd, "On the asymptotic complexity of matrix multiplication," SIAM J. Comput. (To appear.) MR 664715 (83j:68047b)
 [4]
 J. D. Dixon, "Asymptotically fast factorization of integers," Math. Comp., v. 36, 1981, pp. 255260. MR 595059 (82a:10010)
 [5]
 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. 117151. MR 0246815 (40:84)
 [6]
 M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of ," Math. Comp., v. 29, 1975, pp. 183205. MR 0371800 (51:8017)
 [7]
 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)
 [8]
 C. P. Schnorr, private correspondence dated 1982 (communicated to the author by C. Pomerance).
 [9]
 S. S. Wagstaff, Jr., private correspondence dated 19811982.
 [10]
 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, SpringerVerlag, 1979, pp. 328342. MR 564939 (81f:10011)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11Y05,
1104,
11N35
Retrieve articles in all journals
with MSC:
11Y05,
1104,
11N35
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198307016394
PII:
S 00255718(1983)07016394
Article copyright:
© Copyright 1983
American Mathematical Society
