# 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* = *b ^{l}*. 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*mod

^{-1}*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 *m ^{e} *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=b,^{l}m'=-mmod^{-1}Rare required in addition to the inputsm,e,n.

1.M= Mont(m,Rmod^{2}n),result=Rmodnwhere Mont(u,v) isuvRmod^{-1}n

2. Forifromtdown to 0 do the following:

2.1result= Mont(result,result)

2.2 Ife= 1 then_{i}A= Mont(result,M)

3.result= Mont(result,1)

4. Return(result).

Example: Using the Montgomery exponentiation algorithm to compute 5^{9} mod 23:

*e* = 1001_{2} , *m* = 5

*A* = 5 , *result* = 5, *e* = 100_{2}

*A* = 5^{2} mod 23 = 2 , *result* = 5, *e* = 10_{2}

*A* = 2^{2} mod 23 = 4 , *result* = 5, *e* = 1_{2}

*A* = 4^{2} mod 23 = 16 , *result* = 5 · 16 mod 23 = 11 , *e* = null

5^{9} 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.