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

Zachary Harris zacharyharris at hotmail.com
Sat Mar 24 18:47:59 CET 2012


On 03/24/2012 01:00 AM, Zimmermann Paul wrote:
> it is not a bug, since CADO-NFS is not made for such small numbers.
> The file README says explicitly "The integer must not be too small,
> say at least 60 digits".

  Although CADO-NFS is "not made for" such small numbers, there are no
mathematical properties (to my knowledge) that prevent the NFS algorithm
from /working/ on a "small" integer, as long as it is not a prime power.
So although the CADO team would undoubtedly "recommend against it",
nevertheless for the sake of /principle/ I think it is worth noting
that, at least with a little tweaking, CADO /can work/ with numbers
smaller than 60 digits. For example, following is a very simple
hack/cheat that works, even though it is unarguably extremely naive:

    $ factor-cado-nfs-1.1
    000000000000000000000000000000000000000000000000000000057

47 seconds later(!!), I get the factors of this "60 digit" number: 3 and
19. Hooray! Now please, no one needs to point out that this is an
utterly naive (read: "stupid", if you prefer) way to actually obtain the
factors of the number 57. I know. Of course NFS is a silly way to factor
57, and even if for some reason you really, really wanted to use NFS to
factor such a small number, it would be better to set up an appropriate
parameter file rather than just naively prepending zeros to make a
quasi-60-digit number as I have done. But if your goal is to simply play
around with and experience the CADO software, practice using it, and/or
learn a little bit about how the components of NFS work and how they fit
together, naive little experiments like this can actually be helpful for
the learning process.
  In summary, although using CADO/NFS to factor numbers with less than
60 digits may not have value in /professional applications/, doing so
may very well have pedagogical value. Can we say that is a fair
statement, CADO guys?

  So to Andrey, and others with similar questions, I would say the
following:

1) If you are doing research that somehow relates to the polynomial
selection phase of GNFS, and you really have a specialized interest to
see what polynomials CADO comes up for an integer like the one you gave,
I'd bet that you can find a way to make it work for numbers less than 60
digits with a minimal amount of effort. 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. (I have previously noted that
the settings in the existing parameter files are quite ad hoc, anyway.)

On the other hand:

2) If your interest is not research, but simply an application where you
need to factorize numbers in the 20-50 digits range, in Ubuntu/Debian I
would recommend the pyecm package which is very easy to use from the
command line. For the number that you gave in your email, I get the
following factors in roughly 10 seconds on my laptop:

$ pyecm 156785165745616576515615645465156735465487
Factoring 156785165745616576515615645465156735465487:
13
19
241
97499
535234714853801
50471537951410819

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


More information about the Cado-nfs-discuss mailing list