# The Montgomery Method

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

*m ^{e} *mod

*n*

When the operands (*m*,*e*) are relatively small, the result can be computed using a naive method: compute *m ^{e}* and then perform the modular operation. Compute 5

^{3}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. Ife= 0 then return(result).

2. Set A =m.

3. If k_{0}= 1 then setresult=m.

4. Forifrom 1 totdo the following:

4.1 SetA=Amod^{2}n.

4.2 If e_{i}= 1 then setresult=A·resultmodn.

5. Return(result).

Example: Using the square and multiply 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