Re: factor and large prime numbers - Not A Bug.

[Ray Dillinger]

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