[Cado-nfs-discuss] Polyselect problem in cado-nfs-1.1

Zachary Harris zacharyharris at hotmail.com
Sat Mar 24 19:42:03 CET 2012


On 03/25/2012 01:47 AM, Zachary Harris wrote:
> Try adding a new parameter file such as cado/params/params.c42 (for 42
> digit numbers), and set the parameters to "something that seems
> reasonable" based on extrapolation from the other, existing, parameter
> files.

  OK, so obviously more of my naivety is hereby exposed if the
deprecated "polyselect" doesn't even depend on the params files. I don't
know, and hence shouldn't comment further on things I don't understand
and don't have experience with.

  However, in any case, I feel my main point still stands. I /do have
experience/ at what it is like to be a naive user of CADO (which is
where most/all users presumably start). When I first read the README
file (and yes, reading README is always an important and valuable thing
to do), I was confused by the statement:

    The integer must not be too small, say at least 60 digits...

Correct me if I'm wrong, but the integer "must" not be too small only
because corresponding parameter files are not included in the CADO
package for smaller numbers, and the absence of such parameter files for
smaller numbers is only because NFS is not the "best/right"
algorithm/tool to use for these smaller numbers (because other
algorithms are much more efficient for smaller numbers). Nevertheless, I
think it is common for a mathematician to be interested both in the
domain on which an algorithm /works/ (even if it is a horrendously
sub-ideal choice of algorithm) as well as the domain on which the
algorithm is /efficient/.
  Thus I might suggest modifying that portion of the README with
something like the following:

    CADO-NFS is optimized only for numbers above 85 digits, and support
    is not even provided for factorization of integers with less than 60
    digits (since other factorization algorithms are much better for
    these smaller numbers). Also note that it is a good idea to first
    remove small prime factors with a different program that utilizes a
    suitable algorithm for that purpose (such as ECM---or ???) and only
    then to run CADO-NFS on any "hard" remaining factors which have at
    least 60 digits.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/attachments/20120325/d2cce9dc/attachment.html>


More information about the Cado-nfs-discuss mailing list