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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.