Python, реализующий pow() для возведения в степень возведения в квадрат для очень больших целых чисел

Question

Я пытаюсь свернуть свой собственный pow(), который перебирает бит по биту, используя возведение в степень, возводя квадрат http://en.wikipedia.org/wiki/Exponentiation_by_squaring. Были некоторые вопросы в этой области, если это поможет вам в осмыслении этой проблемы:

Difference between the built-in pow() and math.pow() for floats, in Python?

Behavior of Python ** and % operators with big numbers

self made pow() c++

Я преподаю сам Python, так что может быть какой-то простой ошибкой, которую я делаю.

def power(g_base,a,p_mod): 
    x=1; b=[1]; bits = "{0:b}".format(a) 
    for bit in bits: 
    if bit=='1': x *= (((x**2)*g_base)%p_mod) 
    elif bit=='0': x *= ((x**2)%p_mod) 
    else: x *= 1 
    #t = [b.append(((x**2)*g_base)%p_mod) if bit == '1' else b.append((x**2)%p_mod) for bit in bits] 
    return x%p_mod 


a,b,c=5,2,8 
#a,b,c=31,21,12 
print "power(): ",power(a,b,c) 
print "pow(): ",pow(a,b,c) 

Выход прямо с 31,21,12 и неправильно с 5,2,8:

Python 2.7 (r27:82525, Jul 4 2010, 09:01:59) [MSC v.1500 32 bit (Intel)] on win32 
Type "copyright", "credits" or "license()" for more information. 
>>> ================================ RESTART ================================ 
>>> 
power(): 5 
pow(): 1 
>>> ================================ RESTART ================================ 
>>> 
power(): 7 
pow(): 7 
>>> 

Не знаете, где это все пошло трагически неправильно.

Answer 1

Проблема в том, что вы умножаете промежуточные результаты, когда вы делаете x *= (x**2).... Вместо этого вам просто нужно назначить новое вычисляемое значение x. Просто замените x*= с x= следующим образом:

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 

Как примечание стороны, я бы не рекомендовал положить несколько операторов в одной строке, разделенных точкой с запятой (;). Хотя юридический синтаксис, он не очень Pythonic.