A discrete logarithm week

For the third week in a row, this week's Saturday was about qualifying for TopCoder Open 2016. This time the final two lucky contestants were chosen via the Wildcard Round (problems, results, top 5 on the left, parallel round results, my screencast). In the official round, nobody solved 1000, and in both rounds there were only a few solutions to 500. Both were solvable, but together probably just outside the 1 hour and 15 minutes timeframe. xudyh and tourist were the only two official round contestants to get two problems correctly, and thus qualified for the onsite without any close calls. Congratulations!

The current set of 10 finalists (including the changes I'm aware of because of inability to travel) is: Petr, HellKitsune, knightL, eatmore, rng_58, Um_nik, scott_wu, Enot, xudyh, tourist. Please tell if somebody else from this list is not coming!

The reason nobody got the 1000 in the official round is probably twofold: first, the problem statement is long and a bit convoluted. Then, since none of the top scorers went to the 1000 from the start, there were no successful solutions on the scoreboard, which led people to believe that the problem was harder than it really was.

After dissecting the problem statement, it boiled down to this classical algebra task: finding roots modulo a prime. More precisely, given three integers a, k and p, where p is a prime (more precisely, 10⁹+7), find any integer b such that b^k=a (mod p), or report that there isn't any. You also need to do it relatively fast, as one needs to solve this equation 300 times for different values of a (but k and p stay the same). Do you know how to do it?

Thanks for reading, and check back next week for the solution!

Tweet