5
$\begingroup$

Generally speaking, Magma is faster than Sage on several crypto-related computations, however, I have encountered a DLP instance where Sage is significantly faster than Magma.

Take the DLP over $GF(p)$ defined as:

> p := 6361543437356954559572346626686588717116516698890765462106447;
> g := GF(p) ! 1169982245527655985681304256455302750237076631211621733238455;
> h := GF(p) ! 1724031992809937243501910413446727594466297753778440734817181;
> x := 692454894150576523734315040019069833755283562844584533346596;
> g^x eq h;
true
> time Log(g, h); // hangs

Now, observe that $p-1$ is smooth (its factorization contains 2 and 6 primes of 34 bits):

> p - 1 eq &*[2, 4567141973, 12441069709, 12520152383, 15692237597, 16668636287, 17093685347];
true

Yet, Magma hangs on Log(g, h);, while Sage quickly outputs $x$:

sage: p = 6361543437356954559572346626686588717116516698890765462106447
sage: g = GF(p)(1169982245527655985681304256455302750237076631211621733238455)
sage: h = GF(p)(1724031992809937243501910413446727594466297753778440734817181)
sage: x = 692454894150576523734315040019069833755283562844584533346596
sage: g^x == h
True
sage: time discrete_log(h, g)
CPU times: user 3.7 s, sys: 165 ms, total: 3.87 s
Wall time: 3.92 s
692454894150576523734315040019069833755283562844584533346596

Is there any explanation? I have read in the Magma documentation that $2^{36}$ might be a cutoff, but here, the largest prime is below that threshold. A quick and manual implementation of Pohlig-Hellman does not seem to change anything.

My Magma version is 2.23-1 and the same behavior is observed on the online calculator running version 2.25-5.

EDIT: Related subsequent question: How to solve this DLP efficiently in Magma?

$\endgroup$
4
$\begingroup$

Indeed, this is a threshold issue, but the real threshold is $2^{32}$, not $2^{36}$ as documented. You can verify this with the following test:

SetVerbose("FFLog", 2);
repeat p := 2 * (2^32-5) * RandomPrime(10) + 1; until IsPrime(p);
Log(PrimitiveElement(GF(p)), PrimitiveElement(GF(p))^Random(p));
repeat p := 2 * (2^32+15) * RandomPrime(10) + 1; until IsPrime(p);
Log(PrimitiveElement(GF(p)), PrimitiveElement(GF(p))^Random(p));

Unfortunately there does not appear to be a way to call Pohlig-Hellman directly, or at least disable index calculus.

$\endgroup$
2
  • $\begingroup$ Indeed, I also observed the different behavior for 32 bits. With the tracelog, it's even more apparent. Then the related question is: How to solve the given DLP in Magma? It should take only a couple of seconds. $\endgroup$
    – blah blah
    Jul 9 '20 at 20:49
  • $\begingroup$ I'm not sure you can (without waiting); even if you try to do Pohlig-Hellman by hand, you still need to avoid Log for all the smaller logarithms, so it requires implementing the whole thing manually. This is a bug that should be reported to them. $\endgroup$ Jul 9 '20 at 21:34

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.