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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ bolds are mine, and I still wonder why they did not put this into the code. $\endgroup$
    – kelalaka
    Commented Oct 7, 2019 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
    Commented Oct 9, 2019 at 1:10
  • $\begingroup$ @GustavoSchwantz Welcome. $\endgroup$
    – kelalaka
    Commented Oct 9, 2019 at 5:20
  • $\begingroup$ .. and for those who are not familiar with sage? How can it be interpreted in terms of math, please? I.e., base^power % p == target, what is base and what is power? Or how can I calculate it for, e.g., base = 2, given target? $\endgroup$
    – fakub
    Commented Oct 21, 2020 at 13:08
  • $\begingroup$ @kelalaka stupid question. How to use the same software for finite fields having dimensions>1? $\endgroup$
    – user2284570
    Commented Jul 23 at 22:44
0
$\begingroup$

It was hard for me to make sense of the answers as I'm not very familiar with the tool, but finally this is what has worked for me:

I had $q, p = 2q + 1$, both $q, p$ are primes. I needed to find $x$ such that $g^x = X \mod q$ where $g, X, q, p$ are known

  1. Do: 
    ./cado-nfs.py -dlp -ell $q target=$X $p
    This outputs $\log X$
  2. Then, do: 
    ./cado-nfs.py -dlp -ell $q target=$g $p
    which outputs $\log g$
  3. Now you can calculate the answer as $x = \frac{\log X}{\log g} \mod q$. Simply find a modular multiplicative inverse $(\log g)^{-1} \mod q$, so the final answer is $x = (\log X) (\log g)^{-1} \mod q$
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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