Programming Praxis

Today’s exercise is a frequent source of questions at places like Stack Overflow and /r/learnprogramming; it must come from one of the competitive programming sites like SPOJ or UVA. The most common statement of the problem is something like this:

You are given two positive integers P and Q, either of which can be quite large, up to a million digits. Compute P^Q, that is, P raised to the Q power. For your convenience, give the result modulo 10⁹ + 7. For instance, with P = 34534985349875439875439875349875 and Q = 93475349759384754395743975349573495, the expected result is 735851262.

The phrase “for your convenience” is a giveaway that the modulo computation is a trick; that kind of contest site never does anything for your convenience. In fact, due to a corollary of Fermat’s little theorem, P^Q (mod m) ≡ p^q (mod m) where p = P (mod m) and q = Q (mod m − 1). That makes it easy. Compute p and q. Both will be less than 2³², so we can use the Montgomery multiplication algorithm of a previous exercise to make the computation.

Your task is to write a program to perform the big modular exponentiations described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2