|
#REDIRECT[[Modular exponentiation]]
We define a ≡ b (mod c) if (a - b)/c is an integer. Define the function f(x, y, z) ≡ x<sup>y</sup> (mod z), such that f ∈ {0, 1, ... , z - 1}. Then w = f(x, y, z) can be computed efficiently, even when x, y, z > 10<sup>300</sup> 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 z<sup>2</sup>, and the final answer is less than z.
*The method of computing w as x<sup>y</sup> and then reducing w modulo z is not feasible for large numbers. For example, computing f(10, 10<sup>300</sup>, 17) in this way, would involve computing a number w consisting of a 1 followed by 10<sup>300</sup> 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 10<sup>82</sup> 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 10<sup>300</sup> < 16<sup>300</sup> < 2<sup>1200</sup>, and every two steps the exponent is cut in half.
|
