GMP库mpz_powm函数的时间复杂度及实现算法咨询

• 时间复杂度：mpz_powm 的整体时间复杂度由大整数乘法的效率主导，计算 base^exp mod modu 时，其时间复杂度为 O((log base) * (log exp) * log(log base))（基于GMP内置的FFT优化乘法实现）。从指数维度来看，它是O(log exp) 级别，而非线性的O(exp)。

• 实现方式：mpz_powm 确实采用了基于二进制指数分解的高效算法（包含优化的Right-to-left binary method变体），核心逻辑是将指数拆解为二进制形式，通过平方与乘法的组合减少运算次数，确保指数维度的复杂度为对数级，完全适配大指数场景的性能需求。

GMP会根据底数、指数、模数的实际大小自动切换优化策略，但针对大指数场景，绝不会采用O(exp)的线性遍历方式，你可以放心将其应用于大指数模幂运算。

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