Page 275 - Discrete Mathematics and Its Applications

254 4 / Number Theory and Cryptography

2
4
The algorithm successively finds b mod m, b mod m, b mod m,...,b 2 k−1 mod m
and multiplies together those terms b 2 j mod m where a j = 1, finding the remainder
of the product when divided by m after each multiplication. Pseudocode for this algorithm
is shown in Algorithm 5. Note that in Algorithm 5 we can use the most efficient algorithm
Be sure to reduce available to compute values of the mod function, not necessarily Algorithm 4.
modulo m after each
multiplication!

ALGORITHM 5 Modular Exponentiation.

procedure modular exponentiation(b: integer, n = (a k−1 a k−2 ...a 1 a 0 ) 2 ,
m: positive integers)
x := 1
power := b mod m
for i := 0 to k − 1
if a i = 1 then x := (x · power) mod m
power := (power · power) mod m
n
return x{x equals b mod m}

We illustrate how Algorithm 5 works in Example 12.
EXAMPLE 12 Use Algorithm 5 to find 3 644 mod 645.

Solution: Algorithm 5 initially sets x = 1 and power = 3 mod 645 = 3. In the computation
of 3 644 mod 645, this algorithm determines 3 2 j mod 645 for j = 1, 2,..., 9 by successively
squaring and reducing modulo 645. If a j = 1 (where a j is the bit in the jth position in the
binary expansion of 644, which is (1010000100) 2 ), it multiplies the current value of x by 3 2 j
mod 645 and reduces the result modulo 645. Here are the steps used:

2
i = 0: Because a 0 = 0, we have x = 1 and power = 3 mod 645 = 9 mod 645 = 9;
2
i = 1: Because a 1 = 0, we have x = 1 and power = 9 mod 645 = 81 mod 645 = 81;
2
i = 2: Because a 2 = 1, we have x = 1 · 81 mod 645 = 81 and power = 81 mod 645 = 6561 mod 645 = 111;
2
i = 3: Because a 3 = 0, we have x = 81 and power = 111 mod 645 = 12,321 mod 645 = 66;
2
i = 4: Because a 4 = 0, we have x = 81 and power = 66 mod 645 = 4356 mod 645 = 486;
2
i = 5: Because a 5 = 0, we have x = 81 and power = 486 mod 645 = 236,196 mod 645 = 126;
2
i = 6: Because a 6 = 0, we have x = 81 and power = 126 mod 645 = 15,876 mod 645 = 396;
2
i = 7: Because a 7 = 1, we find that x = (81 · 396) mod 645 = 471 and power = 396 mod 645 = 156,816
mod 645 = 81;
2
i = 8: Because a 8 = 0, we have x = 471 and power = 81 mod 645 = 6561 mod 645 = 111;
i = 9: Because a 9 = 1, we find that x = (471 · 111) mod 645 = 36.

This shows that following the steps of Algorithm 5 produces the result 3 644 mod 645 = 36.
▲

2
n
Algorithm 5 is quite efficient; it uses O((log m) log n) bit operations to find b mod m (see
Exercise 58).