快速幂 && 快速乘取模(模拟大数模幂运算,解决乘法爆long long问题)

引言

在 RSA 密码中,当收到密文 C 时,可使用私钥解开,计算公式为

$$ X\ =\ C^{e}\ mod\ n $$

如果想让你计算

$$ 20190324^{823816093931522017}\ mod\ 1001733993063167141 $$

应该如何用代码实现?我们知道,在 Java 里有大数类,Python 依靠其强大的计算性能有些数据甚至可以直接计算。那么在 C/C++ 中应该如何处理?单独用快速幂也会爆 long long ,我们可以采取快速幂调用快速乘进行取模的方法得到结果。
关于快速幂与快速乘的具体原理,可在此博客了解:快速幂 & 快速乘原理讲解(模板)

1 原因分析

首先我们直接用快速幂计算引言中提到的公式:

ksm-ksc-01

不出意料,结果直接溢出。

2 快速幂取模(大数模幂模拟)

因为数据实在是太大了,取模和开 long long 也没办法解决问题,于是可以对快速幂中的乘法运算

ans = (ans * base) % mod;
base = (base * base) % mod;

进行优化,改为快速乘求结果

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    while(b) {
	if(b & 1) {
		ans = (ans + a) % mod;
	}
	a = (a + a) % mod;
	b >>= 1;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1, base = a;
    while(b) {
	if(b & 1) {
		//优化1
		ans = ksc(ans, base, mod) % mod;
	}
	//优化2
	base = ksc(base, base, mod) % mod;
	b >>= 1;
    }
    return ans;
}

3 验证

完整代码:

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const ll mod = 1001733993063167141;

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    while(b) {
	if(b & 1) {
		ans = (ans + a) % mod;
	}
	a = (a + a) % mod;
	b >>= 1;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1, base = a;
    while(b) {
	if(b & 1) {
		ans = ksc(ans, base, mod) % mod;
	}
	base = ksc(base, base, mod) % mod;
	b >>= 1;
    }
    return ans;
}
 
int main() {
    cout << "20190324 ^ 823816093931522017 = " << ksm(20190324, 823816093931522017, mod) << endl;
    return 0;
}

运行结果:

ksm-ksc-02

可以看到数据溢出的问题得到解决,达到了大数模拟的效果。