选出两个不相等的奇质数 p,q，令 n = pq，算出 \varphi(n) = (p - 1)(q - 1)，选出整数 e(1 \le e < \varphi(n),\gcd(e, \varphi(n)) = 1)，再算出 e 在模 \varphi(n) 意义下的逆元 d(1 \le d < \varphi(n))。现有多组数据，每组数据给出整数 n, e, c(15 \le n \le 10^9, 1 \le e, c \le n)，求出每组数据对应的 m = c^d \bmod n。
最后给出题目地址 UVA12799 RSA。
正解思路
这道题的每组数据需要做三件事。
一、求出 \varphi(n)
按照题意，\varphi(n) = (p - 1)(q - 1)，不妨 p < q，又有 n = pq，所以一定有 p < \sqrt{n}，并且 q = \frac{n}{p}。所以，可以从 1 到 \lfloor \sqrt{n} \rfloor 枚举 p（显然，这样的 p 只有一个）。找到后，求出 q = \frac{n}{p}，进而求出 \varphi(n) = (p - 1)(q - 1)。
时间复杂度：\Omicron(\sqrt{n})。
c^{2^i} =
\begin{cases}
c & i = 0 \\
(c^{2^{i-1}})^2 & i > 0
\end{cases}
所以，用一个变量存储答案（初值为 1），从小（0）到大（k - 1）循环枚举整数 i：每次按照上面方法求出 c^{2^i} \bmod n，如果 w_i = 1，则让答案变量乘上 c^{2^i} \bmod n 后对 n 取模。显然，k = \lfloor \log_2 n \rfloor + 1。所以时间复杂度也是 \Omicron(\log_2 n)。
所以，正解思路总的时间复杂度就是 \Omicron(t \sqrt{n})（t 表示询问总数）。
代码
在放代码之前，我想说一些细节：
记得开 long long！！
注意是多组数据，想好读入方式。
好了，接下来放代码。
分治法
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, e, c, r, x, y;
int Phi(int t) {//这道题情况比较特殊，不用打全求欧拉函数的模板
for(int i = 2; ; i ++) {
if(t % i == 0) {
return (i - 1) * (t / i - 1);
}
}
}
void Exgcd(int a, int b) {//拓展欧拉定理求逆元
if(!b) {
x = 1;
y = 0;
return;
}
Exgcd(b, a % b);
int temp = y;
y = x - (a / b) * y;
x = temp;
}
int Quick_pow(int t) {
if(t == 1) return c;
int tmp = Quick_pow(t >> 1);
(tmp *= tmp) %= n;
if(t & 1) (tmp *= c) %= n;
return tmp;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//读入小优化，不介意吧
while(cin >> n >> e >> c) {
r = Phi(n);
Exgcd(e, r);
cout << Quick_pow((x >= 0) ? (x % r) : ((r - (-x) % r) % r)) << endl;
}
return 0;
}
倍增法
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, e, c, r, x, y;
int Phi(int t) {//这道题情况比较特殊，不用打全求欧拉函数的模板
for(int i = 2; ; i ++) {
if(t % i == 0) {
return (i - 1) * (t / i - 1);
}
}
}
void Exgcd(int a, int b) {//拓展欧拉定理求逆元
if(!b) {
x = 1;
y = 0;
return;
}
Exgcd(b, a % b);
int temp = y;
y = x - (a / b) * y;
x = temp;
}
int Quick_pow(int t) {
int tmp = c, s = 1;
while(t) {
if(t & 1) (s *= tmp) %= n;
(tmp *= tmp) %= n;
t >>= 1;
}
return s;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//读入小优化，不介意吧
while(cin >> n >> e >> c) {
r = Phi(n);
Exgcd(e, r);
cout << Quick_pow((x >= 0) ? (x % r) : ((r - (-x) % r) % r)) << endl;
}
return 0;
}