A timing week

The Nov 27 - Dec 3 week started with TopCoder SRM 724 (problems, results, top 5 on the left). snuke, sugim48 and Swistakk had more coding phase points but this round was ultimately decided during the challenge phase, as the easy problem allowed for a lot of incorrect approaches.

On Saturday, Codeforces Round 449 gave ACM ICPC 2017-18 NEERC contestants the last chance to practice, although I'm not sure if many of them did (problems, results, top 5 on the left, analysis). In a somewhat unusual outcome, MrDindows has won the round with less problems than the second place, thanks to an extremely fast solution to the hardest problem — congratulations on the victory!

He's managed to pull this off thanks to being able to squeeze a "naive" quadratic solution under the time limit in a problem with n=100000. This is no small feat, as demonstrated by the fact that just one other contestant was able to do it at all, even within the full two hours. Thankfully he has explained how he was able to achieve this, so that we all can learn the tricks and/or deepen our understanding of compilers!

On Sunday, the said ACM ICPC 2017-18 NEERC took place in St Petersburg (problems, results, top 5 on the left, analysis, broadcast in Russian). The competition was very tight, and Moscow IPT 1 team has earned the first place with 10 minutes to go, in no small part thanks to solving the tricky problem K with just two attempts, whereas the only two other teams to get it accepted required 10 and 14 attempts. Congratulations!

I have set problem H for this round, which was unfortunately the only one left unsolved. This is an interactive problem where you work with a device that takes an a as input and computes a^d mod n using the following pseudocode:

1   modPow(a, d, n) {
2     r = 1;
3     for (i = 0; i < 60; ++i) {
4       if ((d & (1 << i)) != 0) {
5         r = r * a % n;
6       }
7       a = a * a % n;
8     }
9   }

However, instead of receiving the result of the computation, you only receive the time it took the device to execute it, which is computed in the following way: only the multiplications on lines 5 and 7 take nonzero time, and multiplying x by y modulo n takes (bits(x)+1)*(bits(y)+1), where bits(x) is the length of the binary representation of x without leading zeroes.

You know the number n but not the number d, and your goal is to find d after sending at most 30000 requests to the device. You know that n and d were chosen in the following way: first, two prime numbers p and q with bits(p)=bits(q)=30 were picked independently and uniformly at random. Then n was computed as p*q. Then the number m=(p-1)*(q-1) was computed. Then d was picked uniformly at random between 1 and m-1 inclusive, such that it is coprime with m.

Surprisingly, just knowing the time the computation takes for a few requests is enough to extract the value of d. Can you see how to do it?

Thanks for reading, and check back later today!