A Monte Carlo factoring algorithm with linear storage

Schnorr, C.-P.; Lenstra, H. W.

doi:10.1090/S0025-5718-1984-0744939-5

A Monte Carlo factoring algorithm with linear storage
HTML articles powered by AMS MathViewer

by C.-P. Schnorr and H. W. Lenstra PDF

Math. Comp. 43 (1984), 289-311 Request permission

Abstract:

We present an algorithm which will factor an integer n quite efficiently if the class number $h( - n)$ is free of large prime divisors. The running time $T(n)$ (number of compositions in the class group) satisfies $\operatorname {prob}[T(m) \leqslant {n^{1/2r}}] \gtrsim {(r - 2)^{ - (r - 2)}}$ for random $m \in [n/2,n]$ and $r \geqslant 2$. So far it is unpredictable which numbers will be factored fast. Running the algorithm on all discriminants - ns with $s \leqslant {r^r}$ and $r = \sqrt {\ln n/\ln \ln n}$, every composite integer n will be factored in $o(\exp \sqrt {\ln n\ln \ln n} )$ bit operations. The method requires an amount of storage space which is proportional to the length of the input n. In our analysis we assume a lower bound on the frequency of class numbers $h( - m)$, $m \leqslant n$, which are free of large prime divisors.

References

Richard P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), no. 2, 176–184. MR 583032, DOI 10.1007/BF01933190
J. W. S. Cassels, Rational quadratic forms, London Mathematical Society Monographs, vol. 13, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 522835

Divisibility by Small Primes of Class Numbers

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
Carl Friedrich Gauss, Disquisitiones arithmeticae, Yale University Press, New Haven, Conn.-London, 1966. Translated into English by Arthur A. Clarke, S. J. MR 0197380
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878

Vorlesungen über Zahlentheorie

H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260
G. B. Mathews, Theory of numbers, Chelsea Publishing Co., New York, 1961. 2nd ed. MR 0126402

Algorithmes de Factorisation d’Entiers

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
J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, DOI 10.1007/bf01933667
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
R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. MR 700103, DOI 10.1145/359340.359342
J. Sattler and C.-P. Schnorr, Ein Effizienzvergleich der Faktorisierungsverfahren von Morrison-Brillhart und Schroeppel, Computing 30 (1983), no. 2, 91–110 (German, with English summary). MR 698122, DOI 10.1007/BF02280781
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
J. Sattler and C.-P. Schnorr, Generating random walks in groups, Ann. Univ. Sci. Budapest. Sect. Comput. 6 (1985), 65–79 (1987). MR 915225
C.-P. Schnorr, Refined analysis and improvements on some factoring algorithms, J. Algorithms 3 (1982), no. 2, 101–127. MR 657269, DOI 10.1016/0196-6774(82)90012-8

An Improved Composition Algorithm

Acta Arith.

A Comparison of Two Factorization Methods

Horst G. Zimmer, Computational problems, methods, and results in algebraic number theory, Lecture Notes in Mathematics, Vol. 262, Springer-Verlag, Berlin-New York, 1972. MR 0323751