Modular exponentiation is the remainder when an integer b (the base) is raised to the power e (the exponent), and divided by a positive integer m (the modulus); that is, c = be mod m. From the definition of division, it follows that 0 ≤ c < m. For example, given b = 5, e = 3 and m = 13, dividing 53 = 125 by 13 leaves a remainder of c = 8.
That is: Modular exponentiation is efficient to compute, even for very large integers.
On the other hand, computing the modular discrete logarithm – that is, finding the exponent e when given b, c, and m – is believed to be difficult.
This one-way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms.
The time required to perform the exponentiation depends on the operating environment and the processor.
Keeping the numbers smaller requires additional modular reduction operations, but the reduced size makes each operation faster, saving time (as well as memory) overall.
The algorithm performs the iteration thirteen times: The final answer for c is therefore 445, as in the direct method.
The value be can then be written as: The solution c is therefore: The following is an example in pseudocode based on Applied Cryptography by Bruce Schneier.
[2] The inputs base, exponent, and modulus correspond to b, e, and m in the equations given above.
Note that upon entering the loop for the first time, the code variable base is equivalent to b.
However, the repeated squaring in the third line of code ensures that at the completion of every loop, the variable base is equivalent to b2i mod m, where i is the number of times the loop has been iterated.
If a is zero, no code executes since this effectively multiplies the running total by one.
There are four binary digits, so the loop executes four times, with values a0 = 1, a1 = 0, a2 = 1, and a3 = 1.
2, Seminumerical Algorithms, page 463, Donald Knuth notes that contrary to some assertions, this method does not always give the minimum possible number of multiplications.
The smallest counterexample is for a power of 15, when the binary method needs six multiplications.
A recursive algorithm for ModExp(A, b, c) = Ab mod c, where A is a square matrix.
Diffie–Hellman key exchange uses exponentiation in finite cyclic groups.
The above methods for modular matrix exponentiation clearly extend to this context.
In quantum computing, modular exponentiation appears as the bottleneck of Shor's algorithm, where it must be computed by a circuit consisting of reversible gates, which can be further broken down into quantum gates appropriate for a specific physical device.
Furthermore, in Shor's algorithm it is possible to know the base and the modulus of exponentiation at every call, which enables various circuit optimizations.