Discussion related to cado-nfs

[Emmanuel Thomé <Emmanuel.Thome@inria.fr>]

Also, it might be worth knowing that the GF(p^2) test in cado-nfs
currently returns rubbish, and there's quite probably a bug somewhere.
This will be investigated.

http://cado-nfs.gforge.inria.fr/bug.php?21745

E.

On Thu, Feb 28, 2019 at 08:36:04AM +0100, Pierrick Gaudry wrote:
> Hi,
> 
> > > I'm trying to solve DLP in GF(p^2), but I can't understand the meaning 
> > > of
> > > content of the dlog file.
> > > 
> > > for example, I run  
> > > $ ./cado-nfs.py -dlp -ell 101538509534246169632617439
> > > target=92800609832959449330691138186 191907783019725260605646959711
> > > 
> > > when I check the dlog file
> > > 
> > > 0 added column 1
> > > 1 2 0 rat 11263248339990185810045507
> > > 2 2 1 2 12541292681907710540942564
> > > 3 2 1 0 26169984000654153206885433
> > > 4 3 0 rat 43922029394620212666409206
> > > 5 3 1 3 41861160113074041025737154
> > > 6 5 0 rat 19122001771036665804449257
> > > .....
> > > this is what I got.
> > > I can see log(2) = 11263248339990185810045507 from the second line.
> > > but what's the meaning of the third line?
> 
> This is the virtual log of an ideal on the algebraic side. In the
> following line :
>   2 2 1 2 12541292681907710540942564
> 
> - 2 is the index in the table (arbitrary number)
> - 2 is the prime p=2
> - 1 is the side (0 for rat, 1 for algebraic by defautl)
> - 2 is the root 2 of f(x) mod p, where f is the algebraic polynomial
> - 12541292681907710540942564 is the virutal log
> 
> Hence, in mathematical words, 12541292681907710540942564 is the virtual
> log of the ideal (2, x-2) in the number field generated by f(x).
> 
> > > the true quesion is when I run 
> > > $ ./cado-nfs.py -dlp 100000000000000000039 -ell 164354743277891 -gfpext 
> > > 2
> > > I check the dlog file. I got this:
> > > 
> > > 0 2 1 2 1
> > > 2 3 1 3 102959394436835
> > > 4 5 1 5 141624366326326
> > > 6 5 0 4 0
> > > 7 7 1 4 65058838932456
> > > 9 b 0 8 21844599753062
> > > b b 0 6 46520061072202
> > > d d 1 1 0
> > > e 13 1 d 150239015551256
> > > 10 17 1 14 18157130075680
> > > 12 1f 1 14 8740381071634
> > > ......
> > > I can't see the meaning of these lines.
> > > I'm looking forward to your reply.
> 
> When using NFS over an extension field, there is no rational side. Then,
> there are only virtual logarithms of ideals in this table. Relating them
> to discrete logarithms in the target finite field is not immediate. This
> is the purpose of the individual logarithm phase (aka the descent) which
> is not implemented in the current version of cado-nfs for extension
> fields. We have pieces of code here and there that allowed us to finish
> our own computations, but making this fully automatic is a tedious work
> and not a priority for us.
> 
> 
> Tu summarize my answer : sorry, there is no simple way to easily deduce
> final discrete logarithms from the table of virtual logs. I highly
> recommend to read about this virtual log notion in the literature. The
> starting point is the paper by Oliver Schirokauer called "Virtual
> Logarithms" in Journal of Algorithms (2005). You can also use tools like
> Google Scholar to get the papers that cite this one, and read them as
> well.  Understanding virtual logs is, in any case, very important for
> anyone who wants to study the discrete logarithm variants of NFS.
> 
> Best regards,
> Pierrick
> _______________________________________________
> Cado-nfs-discuss mailing list
> Cado-nfs-discuss@lists.gforge.inria.fr
> https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss