[Cado-nfs-discuss] DLP

Emmanuel Thomé Emmanuel.Thome at inria.fr
Thu Oct 13 22:52:59 CEST 2016


Hi.

cado-nfs is right, but maybe the printed info is scarce or misleading.

Here's a verification script.

sage: p=53236943330228380237618624445646085674945074907141464418703
sage: ell=46188898894770668459
sage: target=51415666321640196744601368459935322494639894379132878321944
sage: logtarget=15315241815410699555
sage: log2=39557689199984036821
sage: redlog=ZZ(Integers(ell)(logtarget/log2))
sage: (GF(p)(2)^redlog/target)^((p-1)//ell)
1
sage: (GF(p)(2)^logtarget/GF(p)(target)^log2)^((p-1)//ell)
1

cado-nfs only computes the discrete logarithm of elements of GF(p)^*
modulo ell. And it won't tell you with respect to which base.

So you first have to decide on which generator you want (e.g., 2),
rescale logarithms so that this element has log 1, and then make sure
that your target has the right log mod ell. Which is equivalent to saying
that you have an equality in the subgroup of order ell, or in other words
that when you take the ((p-1)/ell)-th power, you get 1.

The last test of the script is the generic way to do pairwise
verification of two (x,log(x)) pairs.

Best regards,

E.

On Thu, Oct 13, 2016 at 11:43:38PM +0300, Христофор Бобров wrote:
> I run cado nfs with parameters ./cado-nfs.py -dlp 46188898894770668459 target=
> 51415666321640196744601368459935322494639894379132878321944
> 53236943330228380237618624445646085674945074907141464418703.
>  
> The result of the program is
> # sm completed in 0.00 seconds
> Deduced log of (9074579, 7712985, 0) from rel: 13587328245421342694
> Deduced log of (6235561, 483360, 0) from rel: 25480202656792538798
> # p=53236943330228380237618624445646085674945074907141464418703
> # ell=46188898894770668459
> log(2)=39557689199984036821
> log(3)=25673131094860011489
> # target=51415666321640196744601368459935322494639894379132878321944
> log(target)=15315241815410699555
> Final consistency check ok!
>  
> But 46188898894770668459^15315241815410699555 not equal
> 51415666321640196744601368459935322494639894379132878321944
> (53236943330228380237618624445646085674945074907141464418703).
> it has been said that "the logarithms are given in the implicit base used by
> cado-nfs".
> Which describes the generator, to reduce the result to log_{
> 46188898894770668459 }(target).
>  
> 
> Thanks a lot!
> 
> Bobrov.

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



More information about the Cado-nfs-discuss mailing list