Aver 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?

formula

Answer

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
Comments