[Cado-nfs-discuss] Question about DLP

Pierrick Gaudry pierrick.gaudry at loria.fr
Thu Nov 1 16:11:14 CET 2018


Hi,

The result is the discrete logarithm modulo ell. But the order of the
multiplicative group is p-1. To check the result, you need to project on
the subgroup of order ell, by raising everyone to the power (p-1)/ell.

Here are the Sage validation commands for your computation :

p = 191907783019725260605646959711
Fp = GF(p)
ell = 101538509534246169632617439
log2 = 68461024670405903745830817
log3 = 66476914657882357884710743
target = Fp(92800609832959449330691138186)
logtarget = 98216820520868086884824331

logtarget_base2 = logtarget*inverse_mod(log2, ell) % ell
two = Fp(2)
cofac = (p-1)//ell

assert two^(cofac*logtarget_base2) == target^cofac


If you need to recover the full discrete log modulo p-1, then you'll have
to solve it also modulo (p-1)/ell = 1890. This is small enough to be done
by exhaustive search in no time. And then, CRT will give you the answer.

Regards,
Pierrick


On Thu, Nov 01, 2018 at 08:53:33PM +0800, Xs. X. wrote:
> Hello everyone,
> 
> I try to execute the command in README.dlp, and get the result:
> 
> p = 191907783019725260605646959711
> ell = 101538509534246169632617439
> log2 = 68461024670405903745830817
> log3 = 66476914657882357884710743
> target = 92800609832959449330691138186
> log(target) = 98216820520868086884824331
> 
> According to README, I should divide log(target) by log2 to get
> log_2(target). And I get X = log(target)/log2 mod ell
> = 59859158352878681776097204. But 2^X is not equal to target mod p. What
> should I do to get the logarithm of a specific base?
> 
> Thanks a lot!
> 
> Chen Yongyan

> _______________________________________________
> Cado-nfs-discuss mailing list
> Cado-nfs-discuss at lists.gforge.inria.fr
> https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss



More information about the Cado-nfs-discuss mailing list