Abstract
By combining the principles of known factoring algorithms we obtain some improved algorithms which by heuristic arguments all have a time bound O(exp √c ln n ln ln n) for various constants c≥3. In particular, Miller's method of solving index equations and Shanks's method of computing ambiguous quadratic forms with determinant −n can be modified in this way. We show how to speed up the factorization of n by using preprocessed lists of those numbers in [−u,u] and [n−u,n+u],O<<u<<n which only have small prime factors. These lists can be uniformly used for the factorization of all numbers in [n−u,n+u]. Given these lists, factorization takes O(exp[2 (ln n)1/3 (ln ln n)2/3]) steps. We slightly improve Dixon's rigorous analysis of his Monte Carlo factoring algorithm. We prove that this algorithm with probability 1/2 detects a proper factor of every composite n within o(exp √6ln n ln ln n) steps.
This work has been started in Summer 1980 during a stay at the Stanford Computer Science Department. Preparation of this report was supported in part by National Science Foundation grant MCS-77-23738 and by the Bundesminister für Forschung und Technologie.
Chapter PDF
Similar content being viewed by others
References
1 Borodin, A. and Munro, I., The Computational Complexity of Algebraic and Numeric Problems, American Elsevier (1975)
2 Brent, R.P., "Analysis of some new cycle finding and factorization algorithms." Department of Computer Science, Australian National University, 1979
3 de Bruijn, N.G., "On the number of positive integers ≤x and free of prime factors >y, II", Nederl. Akad. Wetensch. Proc. Ser. A 69 (1966), 239–247
4 Diffie, W. and Hellman, M., "New directions in cryptography", IEEE Trans. Information Theory IT-22 (1976), 644–654
5 Dixon, J-D., "Asymptotical fast factorization of integers". Report Department of Mathematics, Carleton University, Ottawa (1978)
6 Gauss, C.F., Disquisitiones Arithmeticae, Leipzig (1801). German translation: Untersuchungen über höhere Arithmetik, Springer, Berlin (1889)
7 Guy, R.K., "How to factor a number", Proc. Fifth Manitoba Conference on Numberical Math. (1975), 49–90
8 Knuth, D.E., The Art of Computer Programming, Volume 2, Seminumerical Algorithms, Addison-Wesley (1969), second edition (1981)
9 Knuth, D.E. and Trabb Pardo, L, "Analysis of a simple factorization algorithm", Theoretical Computer Science 3 (1976), 321–348
10 Legendre, A.M., Theorie des Nombres Tome I, Paris (1978) reprint Blanchard, Paris (1955)
11 Lenstra, H.W., "On the calculation of regulators and class numbers of quadratic fields". Preprint University of Amsterdam (1980)
12 Miller, J.C.P., "On factorization, with a suggested new approach", Math. Computation 29 (1975), 155–172
13 Monier, L., "Algorithmes de factorisation d'entiers", Thèse d'informatique, Université Paris Sud (1980)
14 Morrison, M.A. and Brillhart, J., "A method of factorization and the factorization of F7" Math. Computation 29 (1975), 183–205
15 Pollard, J.M., "Theorems on factorization and primality testing", Proc. Cambridge Phil. Soc. 76 (1974) 521–528
16 Pollard, J.M., "A Monte Carlo method for factorization", BIT 15 (1975), 331–334
17 Rabin, M.O., "Probabilistic algorithms in finite fields", SIAM J. Comp. 9, 2 (1980), 273–280
18 Rivest, R.L., Shamir, A., and Adleman, L., "A method for obtaining digital signatures and public key cryptosystems", Comm. ACM 21,2 (1978), 120–126
19 Rivest, R.L. and Pinter, R.Y., "Using hyperbolic tangents in integer factoring", MIT report (1979)
20 Schnorr, C.P., Refined Analysis and Improvements on some factoring algorithms. Preprint. University Stanford, December 1980
21 Schönhage, A. and Straßen, V., "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), 281–292
22 Shanks, D., "Class number, a theory of factorization and genera", Proc. Symp. Pure Math., American Math. Soc. 20, (1971) 415–440
23 Sieveking, M., "An algorithm for division of power series", Computing 10 (1972), 153–156
24 Straßen, V., "Einige Resultate über Berechnungskomplexität", Jber. Deutsch. Math.-Verein 78, H.1 (1976), 1–8
25 Wunderlich, M.C., "A running time analysis of Brillhart's continuous fraction method", in Springer, Lecture Notes in Math. 751 (1979), 328–342
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1981 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schnorr, C.P. (1981). Refined analysis and improvements on some factoring algorithms. In: Even, S., Kariv, O. (eds) Automata, Languages and Programming. ICALP 1981. Lecture Notes in Computer Science, vol 115. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10843-2_1
Download citation
DOI: https://doi.org/10.1007/3-540-10843-2_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-10843-6
Online ISBN: 978-3-540-38745-9
eBook Packages: Springer Book Archive