Asymptotically fast factorization of integers
Author:
John D. Dixon
Journal:
Math. Comp. 36 (1981), 255260
MSC:
Primary 10A30; Secondary 10A25
MathSciNet review:
595059
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The paper describes a "probabilistic algorithm" for finding a factor of any large composite integer n (the required input is the integer n together with an auxiliary sequence of random numbers). It is proved that the expected number of operations which will be required is for some constant . Asymptotically, this algorithm is much faster than any previously analyzed algorithm for factoring integers; earlier algorithms have all required operations where .
 [1]
N.
G. de Bruijn, On the number of positive integers ≤𝑥 and
free prime factors >𝑦. II, Nederl. Akad. Wetensch. Proc.
Ser. A 69=Indag. Math. 28 (1966), 239–247. MR 0205945
(34 #5770)
 [2]
Gregory
J. Chaitin and Jacob
T. Schwartz, A note on Monte Carlo primality tests and algorithmic
information theory, Comm. Pure Appl. Math. 31 (1978),
no. 4, 521–527. MR 0484750
(58 #4629)
 [3]
William
Feller, An Introduction to Probability Theory and Its Applications.
Vol. I, John Wiley & Sons Inc., New York, N.Y., 1950. MR 0038583
(12,424a)
 [4]
H.
Halberstam, On integers all of whose prime factors are small,
Proc. London Math. Soc. (3) 21 (1970), 102–107. MR 0269614
(42 #4509)
 [5]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [6]
R.
Sherman Lehman, Factoring large integers, Math. Comp. 28 (1974), 637–646. MR 0340163
(49 #4919), http://dx.doi.org/10.1090/S00255718197403401632
 [7]
Gary
L. Miller, Riemann’s hypothesis and tests for primality,
J. Comput. System Sci. 13 (1976), no. 3,
300–317. Working papers presented at the ACMSIGACT Symposium on the
Theory of Computing (Albuquerque, N.M., 1975). MR 0480295
(58 #470a)
 [8]
J.
M. Pollard, Theorems on factorization and primality testing,
Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 0354514
(50 #6992)
 [9]
Michael
O. Rabin, Probabilistic algorithms, Algorithms and complexity
(Proc. Sympos., CarnegieMellon Univ., Pittsburgh, Pa., 1976), Academic
Press, New York, 1976, pp. 21–39. MR 0464678
(57 #4603)
 [10]
R.
L. Rivest, A.
Shamir, and L.
Adleman, A method for obtaining digital signatures and publickey
cryptosystems, Comm. ACM 21 (1978), no. 2,
120–126. MR
700103 (83m:94003), http://dx.doi.org/10.1145/359340.359342
 [11]
Daniel
Shanks, Class number, a theory of factorization, and genera,
1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State
Univ. New York, Stony Brook, N.Y., 1969), Amer. Math. Soc., Providence,
R.I., 1971, pp. 415–440. MR 0316385
(47 #4932)
 [12]
R.
Solovay and V.
Strassen, A fast MonteCarlo test for primality, SIAM J.
Comput. 6 (1977), no. 1, 84–85. MR 0429721
(55 #2732)
 [13]
I.
M. Vinogradov, Elements of number theory, Dover Publications
Inc., New York, 1954. Translated by S. Kravetz. MR 0062138
(15,933e)
 [1]
 N. G. de Brultn, "On the number of positive integers and free of prime factors . II," Indag. Math., v. 28, 1966, pp 239247. MR 0205945 (34:5770)
 [2]
 G. J. Chaitin & J. T. Schwartz, "A note on Monte Carlo primality tests and algorithmic information theory," Comm. Pure Appl. Math., v. 31, 1978, pp. 521527. MR 0484750 (58:4629)
 [3]
 W. Feller, Probability Theory and its Applications. Vol. 1, Wiley, New York, 1950. MR 0038583 (12:424a)
 [4]
 H. Halberstam, "On integers all of whose prime factors are small," Proc. London Math. Soc., (3), v. 21, 1970, pp. 102107. MR 0269614 (42:4509)
 [5]
 D. Knuth, The Art of Computer Programming. Vol. 2, AddisonWesley, New York, 1971. MR 633878 (83i:68003)
 [6]
 R. S. Lehman, "Factoring large integers," Math. Comp., v. 28, 1974, pp. 637646. MR 0340163 (49:4919)
 [7]
 G. L. Miller, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., v. 13, 1976, pp. 300317. MR 0480295 (58:470a)
 [8]
 J. M. Pollard, "Theorems on factorization and primality testing," Proc. Cambridge Philos. Soc., v. 76, 1974, pp. 521528. MR 0354514 (50:6992)
 [9]
 M. O. Rabin, "Probabilistic algorithms," Algorithms and ComplexityNew Directions and Recent Results (J. F. Traub, Ed.), Academic Press, New York, 1976. MR 0464678 (57:4603)
 [10]
 R. L. Rivest, A. Shamir & L. Adleman, "A method for obtaining digital signatures and publickey cryptosystems," Comm. ACM, v. 21, 1978, pp. 120128. MR 700103 (83m:94003)
 [11]
 D. Shanks, Class Number, a Theory of Factorization, and Genera, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R. I., 1970, pp. 415440. MR 0316385 (47:4932)
 [12]
 R. Solovay & V. Strassen, "A fast MonteCarlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 8485; Errata, ibid., v. 7, 1978, p. 118. MR 0429721 (55:2732)
 [13]
 I. M. Vinogradov, Elements of Number Theory, 5th rev. ed., Dover, New York, 1954. MR 0062138 (15:933e)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A30,
10A25
Retrieve articles in all journals
with MSC:
10A30,
10A25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198105950591
PII:
S 00255718(1981)05950591
Article copyright:
© Copyright 1981 American Mathematical Society
