[Cado-nfs-discuss] Question about DLP

Xs. X. zwwynyw at gmail.com
Fri Nov 2 09:34:39 CET 2018


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

On Thu, Nov 1, 2018 at 11:11 PM Pierrick Gaudry <pierrick.gaudry at loria.fr>
wrote:

> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/attachments/20181102/8f64baf3/attachment.html>


More information about the Cado-nfs-discuss mailing list