Discrete exponential function: Difference between revisions

Revision as of 18:25, 30 September 2014

Latest revision as of 14:57, 5 October 2014

(23 intermediate revisions by 7 users not shown)

Line 1:

#REDIRECT[[Modular exponentiation]]

We define a ≡ b (mod c) if (a - b)/c is an integer. Define the function f(x, y, z) ≡ x^y (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³⁰⁰ 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², and the final answer is less than z.