https://www.codingame.com/training/medium/discrete-log-problem
Send your feedback or ask for help here!
Created by @Coni,validated by @JBM,@Niako and @aropan.
If you have any issues, feel free to ping them.
Hello,
I have issues with your problem. I’m trying to solve it in Swift (no one have solved it in Swift before), but I have issues with timeout execution. To do the attack and get the lowest secret key X, I used the modular exponentiation algorithm with G for base, Q for modulus and for X, I use brute force: on a for loop, I try each X from 1 to Q and when G^X % Q = H, I stop and got the key. It worked only on tests and validators 1 and 2. 3rd test said me timeout, solution is not optimized, the last ones after the 3rd had and issue and said nothing is returned.
Need your help please.
Need your help
For your timeout problem, brute force isn’t the correct solution. There is a more efficient way to solve it (the name of the puzzle may help here).
The nothing is returned is a swift issue where it crashes with no output if a calculation overflows (swift appears to generate invalid code to force a crash when you trigger undefined behaviour). You’ll need to find a way to calculate the answers without overflowing to stop it crashing. You’ve already got a modular exponentiation algorithm so other modular arithmetic functions shouldn’t be a problem.
There’s now at least one solution visible in swift (though it’s probably very badly written as I’m not a swift user).
2 Likes
If you call m = ceil(sqrt(q)), expected algorithm is in O(m).
You could find the algorithm with a bit of googleing but if you want to discover it by yourself, here’s some tip:
so, modulo q, you’re looking for a x such that g^x = h.
If the euclidian division of x by m is x = km + r,
you get (g^m)^k * g^r = h,
thus g^r = (g^(-m))^k * h.
Now with some precalculation, you can reduce your search space a lot.
1 Like
Here we have now 2 unknowns: k and x. How to determine k ? If I change Q by m = Int(ceil(sqrt(Double(Q)))) and do the brute force, it won’t work. I’m confuse with your equations, I have no idea to solve them and apply them to get the secret key on each test cases.
I must to get 100% to see your solution. Any hint to implement the discrete logarithm ?
If q is prime, from Fermat’s little theorem you get that g^(q - 1) = 1 so the x you’re looking for is < q.
Therefore, in the euclidian division, k < m and r < m.
Now if you consider the following sets:
A the set of all g^r for r in range(m)
B the set of all (g^(-m))^k * h for k in range(m),
all you need now is finding the element of A that’s also in B.
You could go like this:
for a in A:
for b in B:
if a ==b: break
but complexity would be O(m * m), so you must find a better way to do it.
Note: still by Fermat’s little theorem, g^(-m) is actually g^(q - 1 - m)
1 Like
The numbers of this problem are too big after the test 3. I have found on Google the algorithm of Baby Step-Giant Step. With that, I have passed now the 3 first tests and validators, but won’t work for the others, I have an overflow, even if I used the biggest integer type possible in Swift (Int64), I have no solutions for that. Can I send you my code to have a better comprehension of the issue ?
Computing big powers THEN applying a modulus is always a bottleneck in any language.
Usually there’s a dedicated pow function to do that.
If this pow function doesn’t exist in swift you can implement it like this:
function pow(base, exponent, mod) {
if (exponent == 0) {
return 1;
}
if (exponent & 1 == 1) {
return (pow(base, exponent ^ 1, mod) * base) % mod;
}
return pow(base, exponent >> 1, mod)**2 % mod;
}
Edit: checked your script and you DO implement fast exponentiation so the problem doesn’t come from that.
I think the power -m is faster like this:
let c = fastModularExponentiation(a: g, p: p - 1 - m, n: p)
compared to the one of your script, but it doesn’t change the speed significantly.
Also for the baby step and the giant step you call your fastModularExponentiation function at every step while you could just multiply by the base and apply the modulus at each step.
It might improve the speed.
An other loss of speed could be the contains methed for hashtable being implemented in O(log(N)) instead of O(1) but it seems like Swift implementation is O(1).
So I don’t really know where’s your bottleneck 
1 Like
That’s part of the problem, the modulus can be more than 32 bits so any multiplications can end up needing more than 64 bits. In a similar way to (x**y) % m being possible to do with 64 bit types when the obvious solution would overflow it’s possible to do (x*y) % m without overflow(as long as m is 63 bits or less). The limits are set to make it possible with doubles (53 bit integer accuracy) so javascript has a chance.
1 Like
I didn’t imagine that a simple product would overflow cause numbers didn’t seem that big but it was indeed the problem, when I do all products of his script with a custom product function, then it works fine.
Basically for a product a times b modulus n, you do the following:
starting from a null result, at each step you multiply the last digit of a by b, add that to the result, multiply b by 10 and divide a by 10 (and ofc applying modulus n at each step).
It feels a bit laborious but that way you’re guaranteed too never overflow.
By the way I noticed that the problem went from medium to hard, I’m not sure about that cause it’s really language dependent, in Python for example you just use normal product and pow(a, b, n) and you’re fine ^^"
I think the hard difficulty of this puzzle is now justified. Maybe to solve that the developers of CodinGame have to update the engine of the Swift language and also add some modules to support the big numbers (like Java with BigInteger).
I solved the problem using “Baby step – Giant Step Algorithm” in Python and C#. Although, I think “Pohlig-Hellman’s algorithm” is better for the discrete logs problem