We define a ≡ b (mod c) if (a - b)/c is an integer. Define the function f(x, y, z) ≡ xy (mod z), such that f ∈ {0, 1, ... , z - 1}. Then w = f(x, y, z) can be computed efficiently, even when x, y, z > 10300 by the following recursive algorithm (we assume that the integers x > 0, y > -1, and z > 0):
- if y = 0, return 1.
- if y is even, put u = f(x, y/2, z) and return (u*u) mod z
- return {x*f(x, y - 1, z}} mod z
- Analysis
- The numbers computed are always less than z2, and the final answer is less than z.
- The method of computing w as xy and then reducing w modulo z is not feasible for large numbers. For example, computing f(10, 10300, 17) in this way, would involve computing a number w consisting of a 1 followed by 10300 zeros. If one atom were used to write each zero, then the observable universe would not contain enough atoms to write out w, since it contains fewer than 1082 atoms. The final answer, in any case, will be less than 17, and the above algorithm for the discrete exponential would compute it in fewer than 2400 steps, since 10300 < 16300 < 21200, and every two steps the exponent is cut in half.