# Fast Modular Exponentiation

## October 6, 2014

#### The Problem

… is to compute *b ^{e} (mod m)*, where

*b*,

*e*, and

*m*are positive integers.

*e.g.,* for *b = 2*, *e = 109* and *m = 10 ^{9} + 7*,

*b ^{e} (mod m) = 140625001*

#### A Naive Solution

… would be one that first computes *b ^{e}* and then computes its remainder

*mod m*.

Speaking in terms of the basic arithmetic operations, this method would require *O(e)* multiplications, and a lot of space to store the computed value of *b ^{e}*.

Consider the example given above where *b* is 2 and *e* is 10^{9}. Storing the computed value of *b ^{e}* in this case will require (10

^{9}+ 1) bits! Clearly, such a solution will not cut it with large values of

*b*,

*e*and

*m*.

#### Improving the space bound

The costly *O(log _{2} b^{e})* bound on space can be improved significantly if, instead of computing the remainder at the end, we compute remainders after each multiplication, using the property

*{ p × q } (mod r) = [ p × { q (mod r) } ] (mod r)*

Plugging in values for *b*, *e* and *m* from the example above, we begin multiplying as follows:

*b (mod m) = 2 (mod m) = 2*

*b ^{2} (mod m) = [ b × { b (mod m) } ] (mod m) = [ 2 × 2 ] (mod m) = 4*

*b ^{3} (mod m) = [ b × { b^{2} (mod m) } ] (mod m) = [ 2 × 4 ] (mod m) = 8*

…and so on, till

*b ^{e} (mod m) = [ b × { b^{e - 1} (mod m) } ] (mod m)*

This solution runs in *O(e)* time, using *O(log _{2} (b × m))* space. The space improvement is significant for large values of

*e*.

Here’s a sketch for a recursive function based on the algorithm above, taken from a Wikipedia article:

```
function modular_pow(b, e, m)
c := 1
for e_prime = 1 to e
c := (c * b) mod m
return c
```

#### Improving the time bound

Now that we’ve sufficiently improved the worst-case space bound, let’s do something about the *O(e)* time bound, which can be troublesome for large values of *e*. Consider the binary representation for the exponent *e*:

*e = ( a _{0} × 2^{0} ) + ( a_{1} × 2^{1} ) + … + ( a_{n} × 2^{n} )*, where

*n = log*

_{2}eThus,

*b ^{e} (mod m) = b^{( a0 × 20 ) + ( a1 × 21 ) + … + ( an × 2n )} (mod m)*

*b ^{e} (mod m) = { b^{( a0 × 20 )} (mod m) } × { b^{( a1 × 21 )} (mod m) } × … × { b^{( an × 2n )} (mod m) }*

*b ^{e} (mod m) = { (b^{20} )^{a0} (mod m) } × { (b^{21} )^{a1} (mod m) } × … × { (b^{2n} )^{an} (mod m) }*

At this point, two observations are key:

- When
*a*, the term_{i}= 0*{ (b*reduces to 1^{2i})^{ai}(mod m) } - When
*a*, the same term becomes equal to_{i}= 1*b*, which can be computed iteratively as^{2i}(mod m)*{ b*^{2}(mod m) × b^{2(i - 1)}(mod m) } (mod m)

This leaves us with a fast and space-efficient algorithm running in only *O(log _{2} e)* time and requiring only

*O(log*space. Here’s a sketch of the complete algorithm:

_{2}(b × m))```
function modular_pow(b, e, m)
result := 1
b := b mod m
while e > 0
if (e mod 2 == 1):
result := (result * b) mod m
e := e >> 1
b := (b * b) mod m
return result
```