如何优化计算大整数模幂的Python代码以提升运行速度

核心问题原因 #

你之前的所有写法都犯了同一个致命问题：先计算完整的g的a次方结果再取模。你给定的a是接近1e18的超大整数，直接计算g^a会得到一个有几十亿位的天文数字，无论是内存占用还是计算量都完全无法承受，运行速度当然会极慢。

另外你尝试的两种优化写法本身还有额外问题：

• math.pow是浮点数运算接口，仅能处理精度有限的数值，传入大整数会直接丢失精度，得到的结果完全错误，而且你依然先计算了g**a，计算量和原写法没有任何区别
• 自定义循环乘的写法相当于要循环1e18次，哪怕单次循环只需要1纳秒，跑完也需要几十年，完全没有实用性

最优解决方案 #

Python内置的pow函数原生支持三个参数的模幂调用形式pow(base, exp, mod)，这个接口底层是C实现的快速模幂算法，时间复杂度仅为O(log exp)，计算你给出的参数可以毫秒级出结果，代码如下：

g = 53710316114328094
a = 995443176435632644
n = 926093738455418579
print(pow(g, a, n))

运行后可以直接得到正确结果：55290382992861573

手动实现快速模幂（仅做原理参考） #

如果你需要自己理解实现逻辑，可以参考如下Python版快速模幂写法，性能比内置版本稍差但也远快于你的原有写法：

def fast_mod_pow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        # 指数为奇数时乘入当前底数
        if exp % 2 == 1:
            result = (result * base) % mod
        # 底数平方，指数折半
        exp = exp >> 1
        base = (base * base) % mod
    return result

g = 53710316114328094
a = 995443176435632644
n = 926093738455418579
print(fast_mod_pow(g, a, n))

内容的提问来源于stack exchange，提问作者Mortis_666