Aver - 18 days ago 6
Python Question

# Fast modular exponentiation, help me find the mistake

I am trying to implement a scheme of fast exponentiation. Degree is represented in binary form:

``````def pow_h(base, degree, module):
degree = bin(degree)[2:]
r = 1

for i in range(len(degree) - 1, -1, -1):
r = (r ** 2) % module
r = (r * base ** int(degree[i])) % module

return r
``````

But function is not working properly, where is the mistake?

As I said in the comments, the built-in `pow` function already does fast modular exponentiation, but I guess it's a reasonable coding exercise to implement it yourself.

Your algorithm is close, but you're squaring the wrong thing. You need to square `base`, not `r`, and you should do it after the multiplying step.

``````def pow_h(base, degree, module):
degree = bin(degree)[2:]
r = 1
for i in range(len(degree) - 1, -1, -1):
r = (r * base ** int(degree[i])) % module
base = (base ** 2) % module
return r

#test

for i in range(16):
print(i, 2**i, pow_h(2, i, 100))
``````

output

``````0 1 1
1 2 2
2 4 4
3 8 8
4 16 16
5 32 32
6 64 64
7 128 28
8 256 56
9 512 12
10 1024 24
11 2048 48
12 4096 96
13 8192 92
14 16384 84
15 32768 68
``````

Using `r * base ** int(degree[i])` is a cute trick, but it's probably more efficient to use a `if` statement than exponentiation. And you can use arithmetic to get the bits of `degree`, rather than using string, although `bin` is rather efficient. Anyway, here's my version:

``````def pow_h(base, power, modulus):
a = 1
while power:
power, d = power // 2, power % 2
if d:
a = a * base % modulus
base = base * base % modulus
return a
``````