Discussion related to cado-nfs

["????" <1092016692@qq.com>]

------------------ ???????? ------------------

??????: "????" <1092016692@qq.com>;

????????: 2023??10??9??(??????) ????3:38

??????: "Pierrick Gaudry"<pierrick.gaudry@loria.fr>;

????: ?????? [cado-nfs] Supplement to the discrete logarithm problem for quadratic-extended feild

Dear professor:

I'm solving the discrete logarithm problem on a quadratic extended field with characteristic 45 bits, The parameters of params.p2dd45 I used directly from params.p90, the same goes for p2dd45.hint.

When i run ./cado-nfs.py 100000000000000000000000000000000000000001087 -dlp -ell 5343950341598815341459838431296083 -gfpext 2.

ell is a large factor of p+1.

The following error occurred.

Is there a problem with the parameters inside? How to adjust lpb, lim, mfb0, qrange, rels_wanted and other parameters? What is the meaning of the parameters in.hint and how to adjust them?

Error:Logarithms Reconstruction: Command line was: /home/zp/Math/cado-nfs/build/zp-virtual-machine/filter/reconstructlog-dl -ell 5343950341598815341459838431296083 -mt 16 -log /tmp/cado.it1vr0vl/p2dd45.bwc/K.sols0-1.0.txt -out /tmp/cado.it1vr0vl/p2dd45.dlog -renumber /tmp/cado.it1vr0vl/p2dd45.renumber.gz -poly /tmp/cado.it1vr0vl/p2dd45.poly -purged /tmp/cado.it1vr0vl/p2dd45.purged.gz -ideals /tmp/cado.it1vr0vl/p2dd45.ideal -relsdel /tmp/cado.it1vr0vl/p2dd45.relsdel.gz -nrels 223778 -nsms '1,0' > /tmp/cado.it1vr0vl/p2dd45.reconstructlog-dl.stdout.1 2> /tmp/cado.it1vr0vl/p2dd45.reconstructlog-dl.stderr.1

:Logarithms Reconstruction: Stderr output (last 10 lines only) follow (stored in file /tmp/cado.it1vr0vl/p2dd45.reconstructlog-dl.stderr.1):

Error:Logarithms Reconstruction: antebuffer set to /home/zp/Math/cado-nfs/build/zp-virtual-machine/utils/antebuffer

Error:Logarithms Reconstruction: Warning, log is zero for h = 0

Error:Logarithms Reconstruction: Warning, log is zero for h = 7

Error:Logarithms Reconstruction: Warning, log is zero for h = 12

Error:Logarithms Reconstruction: Warning, log is zero for h = 13

Error:Logarithms Reconstruction: Warning, log is zero for h = 630

Error:Logarithms Reconstruction: Warning, log is zero for h = 4125

Error:Logarithms Reconstruction: Error, no unknown log in rel 84117 and sum of log is not zero, sum is: 2556022473720768550782411652675062

Error:Logarithms Reconstruction:

------------------ ???????? ------------------

??????: "Pierrick Gaudry" <pierrick.gaudry@loria.fr>;

????????: 2023??8??21??(??????) ????3:51

??????: "Paul Zimmermann"<Paul.Zimmermann@inria.fr>;

????: "????"<1092016692@qq.com>;"cado-nfs"<cado-nfs@inria.fr>;

????: Re: [cado-nfs] Supplement to the discrete logarithm problem for quadratic-extended feild

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.