On 07/22/2013 08:09 AM, Sami Kerola wrote:
Any idea what is going on?
...smaller primes can be a lot slower to factor than greater.
The best available factorization algorithms do not take time
exactly correlated to the size of the number they're factoring.
Although we can algorithmically eliminate a lot of guessing, the
basic process still amounts to making and checking a whole lot
of guesses, in an order that corresponds to an estimated
probability that the next guess is correct.
If you get lucky in the first few guesses, then a very large
number factors in microseconds. If not, then factoring a much
smaller number can take a much longer time. This is just a
property of the best known algorithms. In fact, it's a property
of every factoring algorithm I've ever heard of, except for
one which theoretically works on quantum machines but has
never (as far as I remember) actually been used on a number
bigger than six bits.
Not A Bug.
Bear
