python - 请问这个计算a*b%c的函数原理是什么？

Question

def calculate(self, a, b, c):
    if b == 0:return 1
    ans = 1
    while b > 0:
        if b & 1 :
            ans = ans * a % c
        a = a * a % c
        b >>= 1
    return ans

Answer 1

首先这是计算a^b%c或者用Python的话说(a**b) %c
原理是 a*b %c == (a%c * b%c) % c
所以 a**b %c == (a**(b/2) %c * a**(b/2) %c * (b -> if b&1 a else 1) % c) % c