# Sage vs. Magma on DLP

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?

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.

• 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. Jul 9 '20 at 20:49
• 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. Jul 9 '20 at 21:34