This paper presents an algorithm that, given a set of positive integers, nds all the prime factors y of each integer. If there are y=(lg y) O(1) integers, each with (lg y) O(1) bits, then the algorithm takes time (lg y) O(1) per integer. This is useful in congruence-combination methods to compute large factors, discrete logarithms, class groups, etc.
