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

Zimmermann Paul Paul.Zimmermann at loria.fr
Sat Mar 24 20:31:23 CET 2012


       Dear Zachary,

thank you for your mail. I didn't know the "zero padding" trick to construct
fake numbers of 60 digits or more. Funny...

>  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?

you are right. However we prefer to spend our time improving CADO-NFS for
numbers of 100 digits or more, instead of providing support for tiny numbers.

>    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.

thank you, I have modified the README along those lines:

CADO-NFS is optimized only for numbers above 85 digits, and no support will
be provided for numbers of less than 60 digits. 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.

Paul






More information about the Cado-nfs-discuss mailing list