[Cado-nfs-discuss] unbearably slow factorization

Emmanuel Thomé Emmanuel.Thome at inria.fr
Fri Jan 26 17:23:02 CET 2018


On Fri, Jan 26, 2018 at 09:07:19AM -0700, mike at mikepage.us wrote:
> Is this just an issue with suitability of the algorithm? Why is nfs such a poor performer on this input?

Because cado-nfs is an implementation of the number field sieve.

The number field sieve is not always the algorithm you want to use to
factor some given integer. The archetypal example is with "easy" integers
of the form (very very small prime) * (very large primes). As you've
noticed, trial division will do better then.

Similarly, a space shuttle is not necessarily the best means to travel
from Paris to London.

(to factor a 180-digit composite on one single machine, you'll definitely
need some time!)

E.


More information about the Cado-nfs-discuss mailing list