Discussion related to cado-nfs

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

Hello,

The problem is the following:

Cado-nfs DLP machinery for extension fields is not robust at all. In
particular, it implictely assumes that ell, the value modulo which the
discrete logarithms are computed is a prime divisor of the "interesting
part" of the order of the multiplicative group of GF(p^k). Here, when
k=2, it means that ell must be a divisor of p+1.

The rationale for this is that if ell divides p^k-1 but is not a divisor
of the cylcotomic value Phi_k(p), then this is a DLP that can be mapped
in a proper subfield of GF(p^k), and therefore, asking to solve this in
GF(p^k) is very suboptimal.

In the reported problem, ell=101538509534246169632617439 is a divisor of
p-1, so that the DLP can be mapped in GF(p). No need to go to an
extension field.

I'm not saying that there is a theoretical obstruction to run NFS in such
a sub-optimal way, but many things can go wrong in the details of the
implementation, and perhaps in a non-deterministic way.

Conclusion: always take ell dividing p+1, when computing DLP in GF(p^2).
Even like that, please consider that this part of the code is very
experimental, and non-deterministic failures are possible (I have a
few unexpected failures on my todo-list).

Regards,
Pierrick


On Wed, Aug 16, 2023 at 08:51:00AM +0200, Paul Zimmermann wrote:
>        Hi,
> 
> I cannot reproduce, I get with revision 9d69b04:
> 
> zimmerma@coriandre:~/svn/cado-nfs$ ./cado-nfs.py 
> 191907783019725260605646959711 -dlp -ell 101538509534246169632617439 
> -gfpext 2
> ...
> Info:Complete Factorization / Discrete logarithm: The polynomial defining 
> the finite field is 1,-61096303626605014149726703721,1
> 
> Please can you give us more details (version of CADO-NFS used, hardware,
> operating system, compiler)?
> 
> Best regards,
> Paul Zimmermann
> 
> > From: "看见" <1092016692@qq.com>
> > Date: Wed, 16 Aug 2023 14:25:52 +0800
> > 
> > 
> > [1:text/plain Show]
> > 
> > 
> > [2:text/html Hide Save:noname (2kB)]
> > 
> > Dear professor:
> >          When i run ./cado-nfs.py 191907783019725260605646959711 -dlp -ell
> > 101538509534246169632617439 -gfpext 2
> > 
> >   Info:Logarithms Reconstruction: Starting
> > Warning:Command: Process with PID 6024 finished with return code 1
> > Error:Logarithms Reconstruction: Program run on server failed with exit 
> > code
> > 1
> > Error:Logarithms Reconstruction: Command line was:
> > /home/zp/Math/cado-nfs/build/zp-virtual-machine/filter/reconstructlog-dl
> > -ell 101538509534246169632617439 -mt 4 -log
> > /tmp/cado.9xqoti1e/p2dd30.bwc/K.sols0-1.0.txt -out
> > /tmp/cado.9xqoti1e/p2dd30.dlog -renumber
> > /tmp/cado.9xqoti1e/p2dd30.renumber.gz -poly /tmp/cado.9xqoti1e/p2dd30.poly
> > -purged /tmp/cado.9xqoti1e/p2dd30.purged.gz -ideals
> > /tmp/cado.9xqoti1e/p2dd30.ideal -relsdel
> > /tmp/cado.9xqoti1e/p2dd30.relsdel.gz -nrels 37379 -nsms '1,0' >
> > /tmp/cado.9xqoti1e/p2dd30.reconstructlog-dl.stdout.1 2>
> > /tmp/cado.9xqoti1e/p2dd30.reconstructlog-dl.stderr.1
> > Error:Logarithms Reconstruction: Stderr output (last 10 lines only) follow
> > (stored in file /tmp/cado.9xqoti1e/p2dd30.reconstructlog-dl.stderr.1):
> > Error:Logarithms Reconstruction: antebuffer set to
> > /home/zp/Math/cado-nfs/build/zp-virtual-machine/utils/antebuffer
> > Error:Logarithms Reconstruction: Error, no unknown log in rel 16311 and 
> > sum
> > of log is not zero, sum is: 58912568217527066963920738
> > Error:Logarithms Reconstruction:
> >      Looking forward to hearing from you.