4
$\begingroup$

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?

$\endgroup$

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.