[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: factor and large prime numbers - Not A Bug.

**From**: |
Ray Dillinger |

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

**Date**: |
Mon, 22 Jul 2013 09:10:57 -0700 |

**User-agent**: |
Mozilla/5.0 (X11; Linux i686; rv:17.0) Gecko/20130704 Icedove/17.0.7 |

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