Python Implementing Pow() For Exponentiation By Squaring For Very Large Integers

I'm trying to roll my own pow() which goes over a binary bit by bit using exponentiation by squaring http://en.wikipedia.org/wiki/Exponentiation_by_squaring. There were some quest

Solution 1:

The problem is that you are multiplying the intermediate results when you do x *= (x**2).... Instead, you just need to assign the newly computed value to x. Simply replace x*= with x= as follows:

def power(g_base,a,p_mod):
  x=1
  bits = "{0:b}".format(a)
  for i, bit in enumerate(bits):
    if bit=='1': x = (((x**2)*g_base)%p_mod)
    elif bit=='0': x = ((x**2)%p_mod)
  return x%p_mod

As a side note, I would not recommend putting multiple statements in one line separated by a semicolon (;). Although legal syntax, it is not very Pythonic.