How to implement Modular Exponentiation Code

Question

Please I was learning from the book Introduction to algorithm (Chapter 31 page 957) and came across this pseudocode. This pseudocode is how we can implement the modular-exponentiation. The pseudocode is as follows

MODULAR-EXPONENTIATION(a,b,n)

1 c = 0

2 d = 1

3 let <b_k,b_(k-i),....b_0> be the binary representation of b

4 for i = k downto 0

5     c = 2c 

6     d = (d.d) mod n

7     if b_i == 1

8        c = c + 1

9        d = (d.a) mod n

10 return d

Then I tried to implement it in python

def modExpn(a,b,n):
    c = 0
    d = 1
    binary_of_b = f'{b:b}'
    len_of_b = len(binary_of_b)
    for i in range(len_of_b,0,-1):
        val = i - 1
        c = 2 * c
        d = (d * d) %  n
        if binary_of_b[val] == '1':
            c = c + 1
            d = (d * a) % n
    return d

But when I tried running the function (modExpn) with a = 7,b=560 and n = 561 the output I had was 415 but the right answer is 1. Please where am I going wrong ?

Answer 1

You messed up while translating these parts from the pseudocode into actual code:

3 let <b_k,b_(k-i),....b_0> be the binary representation of b

4 for i = k **downto** 0

These instructions say that you should iterate from the left-most digit (b_k) of the binary representation to the right-most (b_0) since you need to go from k down to 0. When you transform, for instance, 8 to binary you get "1000", and in Python the index of the left-most digit will be 0 and not len("1000") - 1 as you are doing. In other words, if you just do:

for bin_digit in binary_of_b:

and later:

if bin_digit == '1':

your code is going to work.