procedure modular exponentiation(b: integer, n = (a-1a-2aa0)2 m: positive integers) x=1 power:= b mod m for i = 0 to k-1 if a;=1 then x = (x. power) mod m power:=(power power) mod m return x{x equals b" mod m} We illustrate how Algorithm 5 works in Example 12. EXAMPLE 12 Use Algorithm 5 to find 3644 mod 645. Solution: Algorithm 5 initially sets x = 1 and power = 3 mod 645 = 3. In the computation of 3644 mod 645, this algorithm determines 32 mod 645 for j = 1, 2, ..., 9 by successively squaring and reducing modulo 645. If a, = 1 (where a, 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 32 mod 645 and reduces the result modulo 645. Here are the steps used: i=0: Because a = 0, we have x = 1 and power = 3² mod 645 = 9 mod 645 = 9; i=1: Because a₁ = 0, we have x = 1 and power = 92 mod 645 = 81 mod 645 = 81; i = 2: Because a = 1, we have x = 1.81 mod 645 = 81 and power = 812 mod 645 = 6561 mod 645 = 111; i = 3: Because a3 = 0, we have x = 81 and power = 1112 mod 645 = 12,321 mod 645 = 66; i = 4: Because a4 = 0, we have x = 81 and power = 66² mod 645 = 4356 mod 645 = 486; i = 5: Because as = 0, we have x = 81 and power = 486² mod 645 = 236,196 mod 645 = 126; i = 6: Because a6 = 0, we have x = 81 and power = 126² mod 645 = 15,876 mod 645 = 396; i = 7: Because a = 1, we find that x = (81-396) mod 645 = 471 and power = 3962 mod 645 = 156,816 mod 645 = 81; i= 8: Because a = 0, we have x = 471 and power = 812 mod 645 = 6561 mod 645 = 111; i=9: Because a,1, we find that x = (471 111) mod 645 = 36. Problem 1: Program a function mod Exp(b, n, m) that computes b" mod m using the algorithm discussed in lecture. The function should satisfy the following: 1. INPUT: • b - positive integer representing the base ⚫ n - positive integer representing the exponent ⚫ m - positive integer representing the modulo 2. OUTPUT: ⚫ the computation of b" mod m EXAMPLE: >> modExp( 3, 644, 645 ) 36