Discussion related to cado-nfs

[Emmanuel Thomé <Emmanuel.Thome@inria.fr>]

On Fri, Jan 26, 2018 at 09:07:19AM -0700, mike@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.