The Montgomery Method
The Montgomery reduction method can be used to speed up modular exponentiation by replacing modular reductions with shift operations.
Choose a suitable R s.t. R > n and gcd(n, R) = 1. Note that in the context of cryptography, n is typically an odd composite of two large primes and this requirement is easily satisfied. The natural choice for R when n is an integer of length l in base b is R = bl. With a suitable choice for R, modular multiplication of two integers x, y can be more efficient. Consider X,Y where X,Y are residues of x,y with respect to R s.t. X = x·R mod n and Y = y·R mod n. The Montgomery reduction of X·Y = X·Y·R-1 mod n = x·y·R mod n. Recall that our choice for R is typically a power of 2.
Suppose we want to compute the result of me mod n using the Montgomery method. The Montgomery reduction can be used for efficient modular exponentiation using this algorithm from Handbook of Applied Cryptography:
The inputs R = bl, m' = -m-1 mod R are required in addition to the inputs m, e, n.
1. M = Mont(m, R2 mod n), result = R mod n where Mont(u, v) is uvR-1 mod n
2. For i from t down to 0 do the following:
2.1 result = Mont(result,result)
2.2 If ei = 1 then A = Mont(result,M)
3. result = Mont(result,1)
4. Return(result).
Example: Using the Montgomery exponentiation 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
Use the simulator to explore different combinations of m, e, n. Generally, the more ones in the binary representation of exponent e, the better Montgomery Method will perform. For small exponents, the standard method is better because there is a computational cost to switch into and out of residues.
References:
P.L. Montgomery, Modular Multiplication without Trial Division, Mathematics of Computation, v. 44, n. 170, 1985, pp. 519-521.
A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, by CRC Press, 1996.