大整数幂模分解公式

ma+b mod q=(ma×mb) q=((ma mod q)×(mb mod q)) mod q\begin{aligned} m^{a+b} \space mod \space q &=(m^a \times m^b) \space q\\ &=((m^a \space mod \space q)\times (m^b \space mod \space q)) \space mod \space q\\ \end{aligned}

证明:

ma+b mod q=tm^{a+b} \space mod \space q = t

ma mod q=t1m^{a} \space mod \space q = t_1

mb mod q=t2m^{b} \space mod \space q = t_2

等价于

ma+b ÷ q=xtm^{a+b} \space \div \space q = x \cdots t

ma ÷ q=x1t1m^{a} \space \div \space q = x_1 \cdots t_1

mb ÷ q=x2t2m^{b} \space \div \space q = x_2 \cdots t_2

其中x,x1,x2x,x_1,x_2为整数

则有

xq+t=ma+bxq+t=m^{a+b}

x1q+t1=max_1 q+t_1=m^at1=max1qt_1=m^a-x_1 q

x2q+t2=mbx_2 q+t_2=m^bt2=mbx2qt_2=m^b-x_2 q

((ma mod q)×(mb mod q)) mod q=(t1×t2) mod q=(ma×mbx2qmbx1qma+x1x2q2) mod q=(ma+bmod q(x2mb+x1ma)q mod q+x1x2q2 mod q) mod q=ma+b mod q ((m^a \space mod \space q)\times (m^b \space mod \space q)) \space mod \space q \\ \begin{aligned} &=(t_1 \times t_2) \space mod \space q\\ &=(m^a \times m^b-x_2qm^b-x_1qm^a+x_1x_2q^2) \space mod \space q\\ &= (m^{a+b}mod \space q -(x_2m^b+x_1m^a)q \space mod \space q +x_1x_2q^2 \space mod \space q ) \space mod \space q\\ &=m^{a+b} \space mod \space q \end{aligned}

证明完毕,即

ma+b mod q=((ma mod q)×(mb mod q)) mod qm^{a+b} \space mod \space q =((m^a \space mod \space q)\times (m^b \space mod \space q)) \space mod \space q

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 求解大整数幂模m^n mod q
int solve(int m, int n, int q) {
// 分解到不可再分
// 如果n==1那么直接输出结果
if (n == 1) return m % q;
// 二分法分解
// 计算s=m^(n/2) mod q
int s = solve(m, n / 2, q);
// 预计算r=(m^(n/2) * m^(n/2)) % q
int r = s * s % q;
// 若为奇数次幂则为(m^(n/2) * m^(n/2) * m) % q
if (n % 2) return (r * (m % q)) % q;
// 偶数次幂则为(m^(n/2) * m^(n/2)) % q
return s * s % q;
}