[Top][All Lists]

[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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]