1
$\begingroup$

I'm using CADO-NFS to calculate discrete logarithm in a finite field GF(p). The problem is when I type

./cado-nfs.py -dlp -ell 101538509534246169632617439 target=92800609832959449330691138186 191907783019725260605646959711

as described in the README.dlp file I just can't understand which of the three values (log2, log3, log(target)) is my discrete logarithm result:

output from CADO

Anyone with some experience with this tool could help me, please? I didn't find anything on the Internet and the documentation that came with CADO say anything about it.

$\endgroup$
1
$\begingroup$

All below from mail thread of [Cado-nfs-discuss] DLP and well explained with a sageMath code.

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.

$\endgroup$
  • $\begingroup$ bolds are mine, and I still wonder why they did not put this into the code. $\endgroup$ – kelalaka Oct 7 at 16:35
  • 1
    $\begingroup$ Thank you very much @kelalaka. Your answer helped me a lot! I also found this other tool sourceforge.net/projects/gdlog for calculate discrete log in GF(p). I'd like a tool with a more easy way to choose the base but I think CADO it'll be enough. $\endgroup$ – Gustavo Schwantz Oct 9 at 1:10
  • $\begingroup$ @GustavoSchwantz Welcome. $\endgroup$ – kelalaka Oct 9 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.