A Monte Carlo Factoring Algorithm With Linear Storage

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.