如何求(a^b)modp,其中p是大质数,指数b是最大不超过2500万位的大整数.好像没法用快速幂,有没有什么用的上的数论公式或简便算法,因为2500万位的数高精度也没办法计算

Question

如何求(a^b) mod p,其中p是大质数,指数b是最大不超过2500万位的大整数.
好像没法用快速幂,有没有什么用的上的数论公式或简便算法,因为2500万位的数高精度也没办法计算

Answer 1

p的位数范围是多少?
如果p的位数还在可容许的范围内(例如几千位?),那么还是可计算的.
因为有Fermat小定理:若(a,p) = 1,则a^(p-1) ≡ 1 (mod p).
所以可先求b除以p-1的余数,设b = (p-1)m+r,其中0 ≤ r < p-1.
则a^b ≡ a^r (mod p).
指数r < p-1,因此如果p的位数不算太大就是可以计算的.
另外乘方运算要在mod p的意义下进行,粗略估计复杂度大概是O(log(p)³)级别.