3¹⁰⁰ mod 15 如何快速计算

先将十进制的100转换为二进制

参考：二进制与十进制互相转换https://www.yuofyou.cn/20200906/1244.html

100₍₁₀₎=1100100₍₂₎

现在要来计算3ⁿ mod 15

n取2的倍数 并且把它们全部计算出来

n取1： 表格中直接写3，这作为基础

n取2：因为对应的二进制是1 所以这里直接把上一个数平方，再乘以基础3
(3¹)² mod 15 = 9 mod 15 = 9 把上一个数平方
9×3 mod 15 = 27 mod 15 =12 再乘以基础3
表格中写12

n取4：因为对应的二进制是0 所以这里直接把上一个数平方

12² mod 15 = 9

直接写9

n取8：因为对应的二进制是0 所以这里直接把上一个数平方

9² mod 15 = 6
表格写6

n取16：因为对应的二进制是1 所以这里直接把上一个数平方，再乘以基础3

6² mod 15 = 6
6 × 3 mod 15 = 3
表格写3

n取32：因为对应的二进制是0 所以这里直接把上一个数平方

3 × 3 mod 15 = 9
表格写9

n取64：因为对应的二进制是0 所以这里直接把上一个数平方

9 × 9 mod 15 = 81 mod 15 = 6

表格写6

到这里表格已经被我们完成了，而这道题的最终答案也就是表格中最后填写的这个数6

3¹⁰⁰ mod 15 = 6

python代码

def int_to_bin(num):
    return list(bin(num))[2:]

"""
Modular exponentiation
returns a ^ b mod n
"""
def exp(a, b, n):
    c = 0
    f = 1 
    bin_b = int_to_bin(b) # 转换二进制
    k = len(bin_b) #取二进制长度看看循环多少次
    for i in range(k):   # Fill this part.
        c = 2*c 
        f =  f*f % n
        if bin_b[i] == '1': 
            c = c+1
            f = f*a % n
           
    return f