python实现快速模幂算法

快速模幂算法的基本思想：

设底数为a，指数为n，计算

将n转化为二进制，例如计算

=

0100 = 4 ，0010 = 2

其中，即以上一次a的平方为本次平方的基数

直白点就是，将指数转换为二进制数

1.求 

2. 令 a = ，重复此步，直至a =  ，此时m < n，(m * m) > n

3.

 

实现代码如下：

#快速模幂算法

def assignment(a,m):
    x = a; n = m; y = 1         #步骤一，赋值
    while n:                    # n == 0，时自动结束算法
        if n == 0:              # 指数为1，则结果为1，直接结束算法
            break
        else:
            if n %2 == 0:       # 指数为偶数，底数a平方，指数n为原来的一半，重复此步骤直至n = 1
                x = x * x
                n = n / 2
            else:               # 指数为奇数时，-1变成偶数，重复偶数的情况
                y = x * y
                n = n - 1
    return y

a = 2 
m = 10
b = 13
res = assignment(a,m)
print("底数为%d，指数幂为%d"%(a,m))     #偶数幂
print("指数为偶数时，快速模幂运算结果为：",res)
res1 = assignment(a,b)
print()
print("底数为%d，指数幂为%d"%(a,b))     #奇数
print("指数为奇数时，快速模幂运算结果为：",res1)

 a为底数，m，b为两个不同的指数幂