Related question: Expected smallest prime factor

Background: Given a toolbox of factorization algorithms (like trial division, ECM, quadratic sieve, GNFS) and a set of large composite numbers, I'm trying to figure out a strategy to find as many factors as possible in a given time. That is, I can choose which number to work on based on how likely I think I am to find a factor, and to switch to a different number when reasonable. For example, after running a probabilistic algorithm such as ECM on a number and having not found a factor, there is a new posterior distribution for the smallest prime factor and thus it might make sense to switch to a different composite.

So: Given a random, uniformly chosen $m$-bit number $N$ which is known to be composite, how is the smallest prime factor of $N$ distributed? Can a formula be given which is robust enough that a useful posterior distribution can be derived from it after running an algorithm which with a given probability rules out small factors?



You must log in to answer this question.

Browse other questions tagged .