[Cado-nfs-discuss] Question about DLP

Pierrick Gaudry pierrick.gaudry at loria.fr
Fri Nov 2 10:23:59 CET 2018


Hi,

The key idea is that in a discrete log equation of the form
  2^x == target mod p,
where x is the unknown, then x can (and must) be seen as an integer
modulo the order of 2 as an element in the multiplicative group of GF(p).

Assuming 2 is a generator (I didn't check on your example), it has order
p-1, so that x must be computed as an element of Z/(p-1)Z. Now, ell is
only a prime factor of p-1, it is not equal to p-1 itself, and cado-nfs
computes the value of x mod ell, not x mod p-1 as you would want if you
need the full discrete logarithm equation. To complete the computation
(in case you need it, which is rare in applications), you need to compute
the value of x modulo the other factors of p-1. Since they are small, any
algorithm will do, even exhaustive search. And then you can reconstruct
the full discrete logarithm by the CRT (or maybe Hensel lifting if they
are prime powers).

What I just described is basically the Pohlig-Hellman algorithm, which is
present in any textbook talking about discrete logarithm, usually in the
first pages of the chapter. See also the Wikipedia webpage:
  https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm

So, I am afraid you'll have to do a bit of study by yourself and read the
basics about discrete logarithm computations.

Maybe you and some other readers of this list wonder why cado-nfs
computes only the mod ell part of the discrete logarithm. This is the
very nature of the NFS algorithm for discrete log. It can only find logs
modulo primes. This is due to the Schirokauer maps (a number theoretic
tool to avoid computing units in the number fields we use) that are usually
defined using some kind of little Fermat theorem which is valid only if
we work modulo a prime. Of course, we could implement a wrapper that 
takes care of all prime factors of p-1, but we prefer to leave that to the
user, just like in the factoring part, we leave it to the user to remove
the small primes that could be present in the number to factor, before
running NFS.

Regards,
Pierrick


On Fri, Nov 02, 2018 at 04:34:39PM +0800, Xs. X. wrote:
> Hi Pierrick,
> 
> In fact I don't quite understand what is discrete logarithm "modulo ell".
> It seems that I have got a relation 2^a == target^b mod p. And I have to
> find another
> relation and solve a congruence equation. Is that correct?
> 
> Thanks a lot
> 
> Chen Yongyan


More information about the Cado-nfs-discuss mailing list