平方总幂法

Question

除了平方和乘法之外，还有这个方法总是平方和乘法，我正在尝试在python中实现它。我的问题是，在搜索过程中，我找到了它的伪代码，here 并且我在 python 中实现了它，但与 pow 函数相比，它没有产生正确的结果。
伪代码可以在上面的 link 或这个 screenshot.

中找到

我的实现是

def square_and_multiply_always(base, exp, mod):
    R0=1
    R1 = base
    c = '{0:b}'.format(exp)
    i=len(c)
    t=0
    while i>=0:
        if(t==0):
            Rt=R0
        elif(t==1):
            Rt=R1
        else:
             print("t != 0 or 1")
        R0=(R0*Rt)%mod
        a=int(c[i-1])
        t=(t^a)
        i=i-1+t
    return R0

Answer 1

我设法找到了我的错误，所以这里有一个正确的代码，供以后在此处结束的搜索使用

def square_and_multiply_always(base, exp, mod):
    R0=1
    R1 = base
    c = '{0:b}'.format(exp)
    i=len(c)-1
    t=0
    c=c[::-1]
    while(i>=0):
        if(t==0):
            Rt=R0
        elif(t==1):
            Rt=R1
        else:
            print("t != 0 or 1")
        R0=(R0*Rt)%mod
        d=int(c[i])
        t=(t^d)
        i=i-1+t
    return R0

平方总幂法

square always exponentiation method

python

exponentiation