Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A Monte Carlo factoring algorithm with linear storage

Authors: C.-P. Schnorr and H. W. Lenstra
Journal: Math. Comp. 43 (1984), 289-311
MSC: Primary 11Y05; Secondary 68Q25
MathSciNet review: 744939
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 68Q25

Retrieve articles in all journals with MSC: 11Y05, 68Q25

Additional Information

Article copyright: © Copyright 1984 American Mathematical Society