Modular Exponentiation Implementation In Python 3

Basically this is a homework question. I'm supposed to implement these two pseudo-code algorithms in Python3. I'm doing something wrong and I can't figure out what (it seems like t

Solution 1:

Your method will only work if b equals 2, which is same as exponentiation by squaring but it will fail in cases with b > 2. Here's how:

Your string n can contain numbers in the range [0,b-1] as it is the representation of number n in base b. In your code, you only check for digit 1, and in the case of b = 7, there can be any digit in the range [0,6]. You have to modify your algorithm as follows :

// take appropriate remainders where required// Correction 1 :
In the for loop,
Check if a[i] = 1, thenx= x * power
elseif a[i] = 2, thenx= x * power^2elseif a[i] = 3, thenx= x * power^3
.
.
.
.
till a[i] = b-1, thenx= x * power^(b-1)
// Correction 2 :
After checking a[i] 
power = power^b and notpower= power^2 which is only good forb=2

You should now get the correct answer.