Discussion related to cado-nfs

[Pierrick Gaudry <pierrick.gaudry@loria.fr>]

On Fri, Jan 26, 2018 at 05:23:02PM +0100, Emmanuel Thomé wrote:
> 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!)

>From the README (admittedly not exactly in the place you would look for
it):
  Note that it is a good idea to remove small prime factors using
  special-purpose algorithms such as trial division, P-1, P+1, or ECM,
  and use CADO-NFS only for the remaining composite factor.

Pierrick