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.

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