Modular Exponentiation - Right-to-left Binary Method

Right-to-left Binary Method

A third method drastically reduces both the number of operations and the memory footprint required to perform modular exponentiation. It is a combination of the previous method and a more general principle called exponentiation by squaring (also known as binary exponentiation).

First, it is required that the exponent e be converted to binary notation. That is, e can be written as:

In such notation, the length of e is n bits. a_i can take the value 0 or 1 for any i such that 0 ≤ i < n - 1. By definition, a_{n - 1} = 1.

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. The inputs base, exponent, and modulus correspond to b, e, and m in the equations given above.

function modular_pow(base, exponent, modulus) result := 1 while exponent > 0 if (exponent mod 2 == 1): result := (result * base) mod modulus exponent := exponent >> 1 base = (base * base) mod modulus return result

Note that upon entering the loop for the first time, the code variable base is equivalent to . However, the repeated squaring in the third line of code ensures that at the completion of every loop, the variable base is equivalent to, where i is the number of times the loop has been iterated. (This makes i the next working bit of the binary exponent exponent, where the least-significant bit is exponent₀).

The first line of code simply carries out the multiplication in . If a_i is zero, no code executes since this effectively multiplies the running total by one. If a_i instead is one, the variable base (containing the value of the original base) is simply multiplied in.

Example: base = 4, exponent = 13, and modulus = 497. Note that exponent is 1101 in binary notation. Because exponent is four binary digits in length, the loop executes only four times:

• Upon entering the loop for the first time, variables base = 4, exponent = 1101 (binary), and result = 1. Because the right-most bit of exponent is 1, result is changed to be (1 * 4)% 497, or 4. exponent is right-shifted to become 110 (binary), and base is squared to be (4 * 4)% 497, or 16.
• The second time through the loop, the right-most bit of exponent is 0, causing result to retain its present value of 4. exponent is right-shifted to become 11 (binary), and base is squared to be (16 * 16)% 497, or 256.
• The third time through the loop, the right-most bit of e is 1. result is changed to be (4 * 256)% 497, or 30. exponent is right-shifted to become 1, and base is squared to be (256 * 256)% 497, or 429.
• The fourth time through the loop, the right-most bit of exponent is 1. result is changed to be (30 * 429)% 497, or 445. exponent is right-shifted to become 0, and base is squared to be (429 * 429)% 497, or 151.

The loop then terminates since exponent is zero, and the result 445 is returned. This agrees with the previous two algorithms.

The running time of this algorithm is O(log exponent). When working with large values of exponent, this offers a substantial speed benefit over both of the previous two algorithms.