[Cado-nfs-discuss] DLP in GF(p^2)

Pierrick Gaudry pierrick.gaudry at loria.fr
Thu Feb 28 08:36:04 CET 2019


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


More information about the Cado-nfs-discuss mailing list