Specific discrete logarithm question

Question

I came across a DL that I need to solve...

5^k = 6361196924231058595008858273263807320 (mod 15860584089531798358308118294328202587) 

The modulus is a 124 bit number, so generic Baby Step - Giant Step would take some $2^{62}$ operations, which is unfeasible on a home PC.

Is there any weakness to it? The modulus is 2 * another huge prime + 1, so definitely not smooth (and susceptible to Pohlig - Hellman).

Apparently, some people solved it on their home PCs in a matter of hours... how? It seems impossible to me.

Answer 1

(12:15) gp > p=15860584089531798358308118294328202587;
(12:15) gp > y=6361196924231058595008858273263807320;
(12:15) gp > x=znlog(Mod(y,p),Mod(5,p))
11473769387225613271575199155876761324
(12:17) gp > ##
  ***   last result computed in 1min, 26,253 ms.
(12:17) gp > Mod(5,p)^x == Mod(y,p)
1
(12:17) gp >
firas@wakaba ~ % cat /proc/cpuinfo |grep 'model name'
model name      : Intel(R) Core(TM) i5-3330 CPU @ 3.00GHz

From the documentation:

This function uses

• a combination of generic discrete log algorithms (see below).

• in $(\mathbb Z/N\mathbb Z)^*$ when $N$ is prime: a linear sieve index calculus method, suitable for $N < 10^{50}$, say, is used for large prime divisors of the order.

The generic discrete log algorithms are:

• Pohlig-Hellman algorithm, to reduce to groups of prime order $q$, where $q \mid p-1$ and $p$ is an odd prime divisor of $N$,

• Shanks baby-step/giant-step ($q < 2^{32}$ is small),

• Pollard rho method ($q > 2^{32}$).

Answer 2

Magma online calculator gave the following [I was interested in CPU time after @fkraiem's answer].

TL;DR: a randomly chosen 200 bit probable prime exceeded CPU time limit of 120 seconds.

code:

x:=6361196924231058595008858273263807320;

p:=15860584089531798358308118294328202587;

F:=GF(p);

b:=F!5; x:=F!x;

"is p prime?",IsPrime(p);

time k:=Log(b,x);

"Check: b^k = ",F!(b^k)," =?=", x;

output:

is p prime? true

Time: 3.490

Check: b^k = 6361196924231058595008858273263807320 =?= 6361196924231058595008858273263807320

Calculations are restricted to 120 seconds. Input is limited to 50000 bytes. Running Magma V2.23-9. Seed: 2717357355; Total time: 3.680 seconds; Total memory usage: 32.09MB.

Magma documentation on DL says:

The different kinds of finite fields in Magma are handled as follows (in this order):

(a) Small Fields (any characteristic): If the largest prime l dividing q - 1 is reasonably small (typically, less than 2^36), the Pohlig-Hellman algorithm is used (the characteristic p is irrelevant).

(b) Large Prime : Suppose K is a prime field (so q=p). Then the Gaussian integer sieve [COS86], [LO91a] is used if p has at least 4 bits but no more than 400 bits, p - 1 is not a square, and one of the following is a quadratic residue modulo p: -1, -2, -3, -7, or -11.

If the Gaussian integer sieve cannot be used and if p is no more than 300-bits, then the linear sieve [COS86], [LO91a] is used. The precomputation stage always takes place and typically requires a lot more time than for computing individual logarithms (and may also require a lot of memory for large fields). Thus, the first call to the function Log below may take much more time than for subsequent calls.

Also, for large prime fields, in comparison to the Gaussian method the linear sieve requires much more time and memory than the Gaussian method for the precomputation stage, and therefore it is only used when the Gaussian integer algorithm cannot be used. See the example H27E3 in the chapter on sparse matrices for an explanation of the basic linear sieve algorithm and for more information on the sparse linear algebra techniques employed.

Taking this as a challenge let's try a 200 bit prime (probable prime)

First precomputation to find a generator:

p = 495998296780695342795805838124611282143307443742260790342431

a probable prime p found in 205 trials

Group order - Orders of these elements are

[ 247999148390347671397902919062305641071653721871130395171215, 0, 247999148390347671397902919062305641071653721871130395171215, 0 ]

a generator found in 4 trials

Take b=3, i.e., L[2];

this trial failed the CPU time limit

Note: I don't have access to my laptop which is at work, to try on the local copy of Magma.