# Binary exponentation with modulo

I have implemented binary exponentiation. Is this good?

def quad_pow(base, exponent, modul):
alpha = (bin(exponent).replace('0b', ''))[::-1]
a = 1
b = base

for i in range(0, len(alpha)):
if int(alpha[i]) == 1:
a = (a * b) % modul
b = (b*b) % modul
return a

• Are you trying to "reinvent-the-wheel"? If not, the most efficient way is pow(base, exponent, modul) (Python 3.x) Commented Apr 9, 2020 at 14:36
• No, I am not. I am aware that there are those functions, but programming doesn't mean that you use those default finished things. I was interested in how to programm this mathematical algorithm. Commented Apr 9, 2020 at 14:58
• "Reinventing the wheel" is a perfectly sound practice; especially when trying to learn programming, or understanding algorithms. We even have a tag for that. Commented Apr 9, 2020 at 15:01

One set of parenthesis are unneeded in this expression:

alpha = (bin(exponent).replace('0b', ''))[::-1]


You could write this as:

alpha = bin(exponent).replace('0b', '')[::-1]


Using [::-1] to reverse the string is nice, but using replace('0b', '') to remove the "0b" from the start first is unnecessary. Using the end field of [start:end:step] would work ... you want to end just before the first character:

alpha = bin(exponent)[:1:-1]


Conversion from a string ("0" and "1") to an integer (0 and 1) is unnecessary when you are just comparing the result to the integer 1. So instead of:

    if int(alpha[i]) == 1:


you could write:

    if alpha[i] == "1":


When you loop over a string, character by character (or any ordered container element by element), using:

for i in range(0, len(alpha)):
if alpha[i] == "1":
...
...


is an anti-pattern in Python. You should loop directly over the container:

for character in alpha:
if character == "1":
...
...


If you need the element and the index, you should use enumerate:

for i, character in enumerate(alpha):
...


but that is not necessary here.

Updated code, with type hints and an example """docstring""":

def quad_pow(base: int, exponent: int, modul: int) -> int:
"""
Efficiently compute (base ^ exponent) % modul

Parameters:
base: The value to raise to the exponent
exponent: The exponent to raise the base to
modul: The modulus to compute the resulting value in

Returns:
The base raised to the exponent, modulo the given modulus
"""

alpha = bin(exponent)[:1:-1]
a = 1
b = base

for character in alpha:
if character == "1":
a = (a * b) % modul
b = (b * b) % modul

return a


PEP-8 Note:

Binary operators should have a space on either side, so (b*b) should be written (b * b).

The string manipulation is avoidable, by working with bits of the exponent directly:

def quad_pow(base, exponent, modul):
a = 1
b = base

while exponent:
if exponent & 1:
a = (a * b) % modul
b = (b * b) % modul
exponent >>= 1
return a