The Montgomery Method

Modular exponentiation is a core operation in several cryptographic algorithms and is of the form:

me mod n

When the operands (m,e) are relatively small, the result can be computed using a naive method: compute me and then perform the modular operation. Compute 53 mod 23:

(5)(5)(5) = 125

125 mod 23 = 10

However with a larger exponent, the size of the intermediate result grows exponentially. When used in cryptography, this operation often calls for exponents greater than 1048 bits in length and the naive method is not practical. To reduce memory consumption, the modular operation can be repeatedly applied because:

(a)(b) mod n = (a mod n)(b mod n) mod n

In addition to limiting the size of the intermediate result, an exponentiation algorithm may take advantage of runs of zero's in the exponent to reduce multiplications. One such algorithm is the square and multiply algorithm (taken from Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone, CRC Press, 1996):

1. Set result = 1. If e = 0 then return(result).
2. Set A = m.
3. If k0 = 1 then set result = m.
4. For i from 1 to t do the following:
4.1 Set A = A2 mod n.
4.2 If ei = 1 then set result = A · result mod n.
5. Return(result).

Example: Using the square and multiply algorithm to compute 59 mod 23

e = 10012 , m = 5
A = 5 , result = 5, e = 1002
A = 52 mod 23 = 2 , result = 5, e = 102
A = 22 mod 23 = 4 , result = 5, e = 12
A = 42 mod 23 = 16 , result = 5 · 16 mod 23 = 11 , e = null
59 mod 23 = 11