Discussion related to cado-nfs

[Bill Winslow <bunslow@gmail.com>]

Hello again!

Thank you very much for the reply.

As for the Msieve/ggnfs vs CADO comparison, I thought for posterity's sake that I should provide some evidence for the assertion: Ben Buhrow's comparison between CADO, yafu/msieve/ggnfs, and yafu's SIQS: http://www.mersenneforum.org/showthread.php?p=423225#post423225

And secondly, a paper that describes factoring as a service via AWS. In particular section 3 and a few parts of section 4 compare Msieve and CADO (they used the CADO siever, and seem to not have considered the ggnfs siever). The whole paper is still worth reading though. http://fc16.ifca.ai/preproceedings/19_Valenta.pdf

Regarding the control issue, even ignoring the parameter problem since it can indeed be worked around, is it possible to run only certain portions of poly selection? The scripts/cadofactor/README indicates that we can "import" external polys, but it seems while importing does control which phase is started with, it's not possible to (e.g.) do just size optimization, and not root optimization. Additionally, it might be nice to extend control over the rote searching stage before size optimization. As I indicated above, GPU-enabled Msieve tends to outperform CADO in a given wallclock time merely because it can do so much more rote searching (I believe in depth per leading coefficient, though honestly the details are largely beyond me). In fact in Msieve, size optimization is considered stage 2 (as is root optimization, though I think in practice most people versed in GPU-Msieve usage think of the process as three different stages). So one possible avenue to explore is using GPU-Msieve to do the searching, then importing those results into CADO for size and root optimizing (though IIRC the intermediate data between the two would be massive). (Now that I think about it, I recall that I did some similar work for RSA-896 some years ago; what's the current status on factoring it? Has anyone decided to move forward with sieving, or is there not yet a suitable polynomial...? Lack of resources or interest...?)

At any rate, the command you pasted, and the similar command from the main README, don't seem to accomplish much: https://gist.github.com/dubslow/5afccd93ebc77fa8ead9

It seemingly hangs there with no CPU time used. Do I need to specify slaves.hostname=localhost? The README seemed to indicate that wasn't necessary, but maybe I've misunderstood something somewhere. Actually, looking at it closer, it seems to think that size optimization is already done? I have no idea why it would think that...

Thanks again for all your help, it is very much appreciated.

Bill

On Thu, Mar 17, 2016 at 4:14 AM, paul zimmermann <Paul.Zimmermann@inria.fr> wrote:

       Hi Bill,

> Date: Thu, 17 Mar 2016 03:49:29 -0500
> From: Bill Winslow <bunslow@gmail.com>
>
> Hello everyone.
>
> I am Dubslow from http://mersenneforum.org, and I've just downloaded CADO
> for the first time to try out its polyselect capabilities on a C195 from
> aliquot sequence 4788. The general consensus around MersenneForum is that
> all stages of CADO-NFS are marginally inferior to msieve/ggnfs, with the
> notable exception of the GNFS polynomial selection.

good to know!

> For most large GNFS tasks these days, the folks over at MF tend to use
> GPU-enabled Msieve polyselect, which despite an inferior algorithm,
> benefits from the ~100x speedup of GPUs. As I (and at least one other)
> don't have CUDA installed, I'd like to play around with CADO's polyselect.
>
> I've done what I think is reasonable efforts to read all the documentation,
> but so far I've been unable to find out how to get the scripts to not even
> think about sieving/post-processing in the slightest. My parameters file
> has the following (polyselect params copied from the C190 example, save for
> I):
>
> tasks.factorbase.run = false
> tasks.sieve.run = false
> tasks.filter.run = false
> tasks.linalg.run = false
> tasks.sqrt.run = false
>
> tasks.polyselect.degree = 5
>
> tasks.polyselect.P = 10000000
> tasks.polyselect.admax = 5e7
> tasks.polyselect.adrange = 5e5
> tasks.polyselect.incr = 60
> tasks.polyselect.nq = 1000
> tasks.polyselect.nrkeep = 1000
> tasks.I = 15
>
> And yet, despite my best efforts, I get the following error when I launch
> cado-nfs.py:
>
> Info:HTTP server: Using non-threaded HTTPS server
> Debug:Generate Factor Base: Enter Task.__init__(factorbase)
> Debug:Generate Factor Base: state = {}
> Critical:Parameters: Required parameter alim not found under path
> tasks.sieve.factorbase
> Traceback (most recent call last):
>   File "../cado-nfs.py", line 102, in <module>
>     path_prefix = [])
>   File "../scripts/cadofactor/cadotask.py", line 5105, in __init__
>     path_prefix=sievepath)
>   File "../scripts/cadofactor/cadotask.py", line 2387, in __init__
>     path_prefix=path_prefix)
>   File "../scripts/cadofactor/cadotask.py", line 987, in __init__
>     self.params = self.parameters.myparams(self.paramnames)
>   File "../scripts/cadofactor/cadoparams.py", line 746, in myparams
>     return self.parameters.myparams(keys, path)
>   File "../scripts/cadofactor/cadoparams.py", line 169, in myparams
>     self._convert_types(result, keys, splitpath, found_at_path)
>   File "../scripts/cadofactor/cadoparams.py", line 584, in _convert_types
>     raise KeyError(msg)
> KeyError: 'Required parameter alim not found under path
> tasks.sieve.factorbase'
>
> Why does cado-nfs insist on thinking about factorbase and sieving
> parameters when I will be doing nothing of the sort? In Msieve/Yafu I can
> select polyselect only with some variant of -np, -np1, -nps, -npr, and it
> doesn't require nor produce any sieving parameters whatsoever.
>
> I'm reasonably certain that I could do just fine with some made up sieve
> parameters, but it still seems to me that I should be able to run
> individual parts of the overall algorithm without thinking about parts I
> know I won't be doing.
>
> Of course there's a decent chance I've overlooked something, but a minor
> inquiry over at MF yielded nothing similar:
> http://mersenneforum.org/showthread.php?p=429303#post429303
>
> Thank you for your consideration and assistance.
>
> Bill

indeed currently you have to provide all parameters, even if you only want to run
polynomial selection with CADO-NFS. But I do not consider this as a serious
limitation, since you can simply do:

zimmerma@tomate:/tmp/cado-nfs$ ./cado-nfs.py --parameters parameters/factor/params.c190 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
...

Best regards,
Paul

PS: I've just added in the git version parameter files for 195 and 200 digits
(not really optimized so far)