On the distribution of running times of certain integer factoring algorithms

Abstract

There are several algorithms for computing the prime decomposition of integers whose running times essentially depend on the size of the second largest prime factor of the input. For several such algorithms, we give uniform estimates for the number of inputs n with 1 ≤ n ≤ x for which the algorithm will halt in at most t steps. As a consequence we derive the best known lower bound for the number of integers n ≤ x that can be completely factored in random polynomial time. © 1989.