Aver - 4 months ago 23

Python Question

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?

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
```