Discussion related to cado-nfs

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

Dear Nimrod,

Adding manually a missing hint or parameter file is indeed the right
thing to do when a particular size of input is not yet supported.
Therefore, I confirm that you did the right thing.

The problem is that already for 30 digits, it is hard to find parameters
that are robust. And it gets even worse for smaller sizes ! Things that
almost never occur for large sizes tend to occur more frequently and are
not taken properly into account in the implementation.

Honestly, the number field sieve algorithm has a hard time computing
discrete logarithms modulo small primes. I recommend that you use GP/Pari
(or Sagemath as a front-end to it) for this kind of computation. They use
an algorithm that is asymptotically slower for large sizes, but that will
be faster here (or at least take a comparable time), and furthermore it
will be much more robust.

Apart from that, I recommend to use the git version. The 2.3.0 release is
pretty old, now, and a lot of stuff was added since then. In particular,
dlp parameters for sizes between 30 and 100 digits are now much better
than at the time of 2.3.0.

Regards,
Pierrick


On Thu, Dec 05, 2019 at 11:27:03AM +0200, Nimrod Aviram wrote:
> Dear CADO-NFS Team,
> 
> Thanks for making this awesome piece of software available! :-)
> I'm trying to use CADO-NFS to compute discrete log modulo relatively small
> primes.
> e.g.:
> ./cado-nfs.py -dlp -p parameters/dlp/params.p30 -ell 891795089922643
> target=108133651678831697130 152596841426843289017
> results in a "no hint file found for p21" error.
> 
> I've also tried to manually patch the code to use the p30 hint file in this
> case, and got the error at the end of this mail.
> 
> What would be the easiest way to add support for discrete log modulo
> smaller primes to CADO-NFS?
> 
> (This is on cado-nfs 2.3.0, built simply with "make". Please let me know if
> I should include more build information.)
> 
> thanks a lot,
> Nimrod
> 
> =========
> The long error when using the p30 hint file:
> 
> Warning:Command: Process with PID 9692 finished with return code 2
> Error:Linear Algebra: Program run on server failed with exit code 2
> Error:Linear Algebra: Command line was:
> /localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/bwc.pl :complete
> 'thr=8' 'm=4' 'n=2' 'nullspace=right'
> 'matrix=/tmp/cado.ljtgcvwc/p30.sparse.bin' 'rhs=/tmp/cado.ljtgcvwc/p30.sm'
> 'prime=891795089922643' 'wdir=/tmp/cado.ljtgcvwc/p30.bwc'
> 'cpubinding=/localwork/false_start/cado-nfs-2.3.0/parameters/misc/cpubinding.conf'
> 'cantor_threshold=2048' > /tmp/cado.ljtgcvwc/p30.bwc.stdout.1 2>
> /tmp/cado.ljtgcvwc/p30.bwc.stderr.1
> Error:Linear Algebra: Stderr output follows (stored in file
> /tmp/cado.ljtgcvwc/p30.bwc.stderr.1):
> b'#############################################################################\n/localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/prep
> nullspace=right mpi=1x1 thr=2x4 prime=891795089922643 interval=200
> cpubinding=/localwork/false_start/cado-nfs-2.3.0/parameters/misc/cpubinding.conf
> m=4 wdir=/tmp/cado.ljtgcvwc/p30.bwc
> matrix=/tmp/cado.ljtgcvwc/p30.sparse.bin rhs=/tmp/cado.ljtgcvwc/p30.sm
> n=2\nWriting balancing data to
> p30.sparse.2x4.bin\n#############################################################################\n/localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/secure
> nullspace=right mpi=1x1 thr=2x4 prime=891795089922643 interval=200
> cpubinding=/localwork/false_start/cado-nfs-2.3.0/parameters/misc/cpubinding.conf
> m=4 wdir=/tmp/cado.ljtgcvwc/p30.bwc
> matrix=/tmp/cado.ljtgcvwc/p30.sparse.bin
> n=2\n#############################################################################\n/localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/krylov
> nullspace=right mpi=1x1 thr=2x4 prime=891795089922643 interval=200
> cpubinding=/localwork/false_start/cado-nfs-2.3.0/parameters/misc/cpubinding.conf
> m=4 wdir=/tmp/cado.ljtgcvwc/p30.bwc
> matrix=/tmp/cado.ljtgcvwc/p30.sparse.bin n=2 ys=0..1
> start=0\n#############################################################################\n/localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/krylov
> nullspace=right mpi=1x1 thr=2x4 prime=891795089922643 interval=200
> cpubinding=/localwork/false_start/cado-nfs-2.3.0/parameters/misc/cpubinding.conf
> m=4 wdir=/tmp/cado.ljtgcvwc/p30.bwc
> matrix=/tmp/cado.ljtgcvwc/p30.sparse.bin n=2 ys=1..2
> start=0\n#############################################################################\n/localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/acollect
> nullspace=right prime=891795089922643 interval=200 m=4
> wdir=/tmp/cado.ljtgcvwc/p30.bwc n=2
> --remove-old\n#############################################################################\n/localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/plingen_pz
> lingen_threshold=10 lingen_mpi_threshold=10 split-output-file=1
> afile=A0-2.0-400 ffile=F mpi=1x1 prime=891795089922643 m=4
> wdir=/tmp/cado.ljtgcvwc/p30.bwc rhs=/tmp/cado.ljtgcvwc/p30.sm n=2\nERROR:
> all solutions have zero contribution on the RHS vectors -- we will just
> output right kernel vectors (maybe use allow_zero_on_rhs
> ?)\n/localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/plingen_pz:
> exited with status 1\naborted on subprogram error at
> /localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/bwc.pl line 512,
> <F> line 1.\n\t...propagated at
> /localwork/false_start/cado-nfs-2.3.0/build/ssd/linalg/bwc/bwc.pl line
> 1406, <F> line 1.\n'
> Traceback (most recent call last):
>   File "./cado-nfs.py", line 122, in <module>
>     factors = factorjob.run()
>   File "./scripts/cadofactor/cadotask.py", line 5429, in run
>     last_status, last_task = self.run_next_task()
>   File "./scripts/cadofactor/cadotask.py", line 5504, in run_next_task
>     return [task.run(), task.title]
>   File "./scripts/cadofactor/cadotask.py", line 4106, in run
>     raise Exception("Program failed")
> Exception: Program failed

> _______________________________________________
> Cado-nfs-discuss mailing list
> Cado-nfs-discuss@lists.gforge.inria.fr
> https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss