重复造轮子可不是什么很好玩的事情，但是奈何自己记性实在是差，不如写下来方便自己看和记忆。
暂时是没什么问题了，大概（？有的话欢迎指出:)
约定记号
- $\varphi(n)$ 表示欧拉函数，具体含义是「小于 $n$ 的正整数中和 $n$ 互质的数的个数」。其中还定义 $\varphi(1) = 1$；
- $a \in \mathbb{P}$ 表示 $a$ 属于所有质数所构成的集合，即 $a$ 为质数。
- $b \mid a$ 表示 $b$ 为 $a$ 的因子，相应地，$b \nmid a$ 表示 $b$ 不为 $a$ 的因子也即 $\gcd(a, b) = 1$。
- $\operatorname{inv}(b,a)$ 表示当 $b \nmid a$ 时， $b$ 对 $a$ 的逆元。具体有 $\operatorname{inv}(b,a)\cdot b = \lambda a + 1, \lambda \in \mathbb{Z}$，也即 $\operatorname{inv}(b,a)\cdot b \equiv 1 \pmod a$
公私钥生成过程
为了让 Alice Margatroid 与 Sponge Bob （大雾）实现目前这个阶段比较难破解的加密通信，可以考虑经典的 RSA 加密。步骤如下：
- 选取两非常大的且不相等的质数 $p, q$，计算两者乘积 $n = p \times q$ 以及其欧拉函数 $m = \varphi(n) = (p - 1)(q - 1)$；
- 让发送方选取一个数 $e$，要求这个数满足 $1 < e < m,\ e \nmid m$；
- 计算 $d = \operatorname{inv}(e, m)$。
至此生成公钥对和私钥对，分别为 $(n, e)$，$(n, d)$。
加解密过程
明文往往通过转换形成十六进制数，再通过十进制转换而变成一个比较大的数。将明文形成的这个数记为 $x$，密文记为 $y$。
那么根据公私钥生成过程，存在关系 $\begin{cases} y \equiv x^e \pmod{n}, & \mathsf{encrypt}\\ \\ x \equiv y^d \pmod{n}, & \mathsf{decrypt}\end{cases}$。
加密过程是人为规定的。我们只需要来考虑解密的正确性。
$$\begin{aligned} & x \equiv y^d \equiv x^{ed} \pmod{n} \\ \because \ & d = \operatorname{inv}\Big(e, \varphi(n)\Big) \\ \therefore \ & ed = \lambda \varphi(n) + 1, \lambda \in \mathbb{Z} \\ \therefore \ & \boxed{x \equiv x^{\lambda \varphi(n) + 1} \pmod{n}} \end{aligned}$$
假定大家都不知道这个被框起来的式子是已经被证明了的，我们来看一下如何证明。
欧拉函数、剩余类与欧拉定理
欧拉函数
首先由定义，当 $n\in \mathbb{P}$ 时，必然有 $\varphi(n) = n - 1$。
那么对于上面的 $n$，我们完全可以考虑 $n^k, k \in \{x |x > 1, x \in \mathbb{Z}\}$ 的欧拉函数。
此时可以发现，只要含有 $n$ 的数，和 $n^k$ 都必定有最大公因数 $n$。
所以只要考虑 $n, 2n, 3n, \ldots, (n^{k - 1} - 1 )n, n^{k - 1} \cdot n$ 就不难发现 $n^k$ 一共有 $n^{k - 1}$ 个因数。
所以有 $\varphi(n^k) = n^{k} - n^{k-1} = n^{k-1}(n-1)$。
同时注意到 $a\neq b; \gcd(a,b) = 1$ 且 $a,b\in\mathbb{P}$ 时，由容斥关系可以得到 $\varphi(ab) = ab - a - b + 1 = (a - 1)(b - 1) = \varphi(a)\varphi(b)$。
由算术基本定理可得 $n = p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}; 1 \leqslant i \leqslant m, p_i \in \mathbb{P}$。
从而有 $\varphi(n) = \displaystyle\prod\limits_{i = 1}^m \varphi(p_i^{k_i}) = \displaystyle\prod\limits_{i = 1}^m p_i^{k_i-1}(p_i - 1) = \displaystyle\prod\limits_{i = 1}^m p_i^{k_i} (1 - \dfrac{1}{p_i}) = n \displaystyle\prod\limits_{i = 1}^m (1 - \dfrac{1}{p_i}) = n \displaystyle\prod\limits_{p_i \mid n} (1 - \dfrac{1}{p_i})$。
题外话：到了莫比乌斯反演那边，欧拉函数与乘法卷积还存在关系 $n = \varphi * 1 = \displaystyle\sum\limits_{d\mid n}\varphi(d)$。
代码常写常新（
// 单个数的。
inline int Phi(int __n) {
int res = __n, i = 2;
for(; i * i <= __n; i ++)
if(__n % i == 0)
{
res = res / i * (i - 1);
while(__n % i == 0) __n /= i;
}
if(__n > 1) res = res / __n * (__n - 1);
return res;
}
// 多个数的。
const int N = 1E6 + 10;
bool st[N];
int prime[N], cnt;
int phi[N], mu[N];
void prime() {
mu[1] = 1;
for(int i = 2; i <= N; ++i)
{
if(!st[i]) prime[cnt++] = i, phi[i] = i - 1, mu[i] = ~0;
for(int j = 0; j < cnt and prime[j] * i <= N; ++j)
{
st[i * prime[j]] = 1;
if(i % prime[j] == 0){
phi[prime[j] * i] = phi[i] * prime[j];
break;
}
mu[prime[j] * i] -= mu[i];
phi[prime[j] * i] = phi[i] * (prime[j] - 1);
}
}
}
剩余类、完系、缩系与欧拉定理
直观来讲，从 $0\sim 100$ 一个一个挑出数字来除以 $7$ 并保留其余数，不难看见 $7$ 的余数是会反复出现的。
为此，将所有 余数一致 的数归纳到一个集合中形成剩余类（亦称「同余类」）并令余数 $r$ 充当代表这一集合的代表元素，那么对于这一剩余类有比较直观的表示： $\bar{r}_7 = \{m \in \mathbb{Z}| 7m + r \}$。
那么进一步加深抽象程度，对于所有除数 $n$，剩余类可以表示为 $\bar{r}_n = \{m \in \mathbb{Z}| nm + r \}$。
那么，从以下 $\bar{0}_n, \bar{1}_n, \bar{2}_n, \ldots, \overline{n-1}_n $ 的每一个剩余类中挑选出任意一个数，并将这些数构成新的集合，那么这时这些数构成的集合被定义为模数是 $n$ 的完全剩余系（完系）。
而显然，$\{0,1,2,\ldots,n-1\}$ 是模数为 $n$ 的最小非负完系。这一最小非负完系与模 $n$ 加（$+_n$） 构成整数域上的群 $\mathbb{Z}^+_n = \dfrac{\mathbb{Z}}{n\mathbb{Z}} = \langle\{0,1,2,\ldots,n-1\}, +_n\rangle$。
那个商群的正规写法应该是 $\mathbb{Z}/n\mathbb{Z}$。
以其代表元素来抽象表示我们所选取的这些数，那么再从完全剩余系 $\{\bar{0}_n, \bar{1}_n, \bar{2}_n, \ldots ,\overline{n-1}_n\}$ 中挑选出所有与模数互质的数构成新集合，那么此时把得到的这种集合被称为「缩剩余系（缩系）」。
取出缩系 $\{x_1, x_2, \ldots, x_{\varphi(n)}\}$ 中的所有数，然后让满足 $\gcd(a, n) = 1$ 的数 $a$ 依次与这些数相乘，得到集合 $\{ax_1,ax_2,\ldots, ax_{\varphi(n)} \}$。
将 $a$ 通过乘法乘进去之后不能保证集合依然保持原本的元素不变，但从某种程度上，它们只是“偏移”了位置。
具体而言，由于缩系中的所有数与 $n$ 互质，显然 $a$ 一定在缩系中。
那么，这个时候我们只需要证明「缩系与相乘后模上 $n$ 的运算能构成交换群」，就能说明 $\overbrace{(ax_1) (ax_2)\cdots (ax_{\varphi(n)})}^{\operatorname{Commutative \ and \ Associative.}} \equiv x_1 x_2\cdots x_{\varphi(n)} \equiv a^{\varphi(n)}x_1 x_2\cdots x_{\varphi(n)} \pmod n$，进而就可以有 $a^{\varphi(n)} \equiv 1 \pmod n$。
事实上人家直接把「模 $n$ 缩剩余系关于乘法模 $n$ 构成阿贝尔群」1当作定理来用。
证明一个代数系统是群，只需要说明它能满足群的四大公理就行。为了强调记号，将「与相乘后模上 $n$ 的运算」记为 $\circ$。
- 封闭性：
由于 $\forall x_i,x_j \in \{x_1, x_2, \ldots, x_{\varphi(n)}\}, \gcd(x_i, n) = \gcd(x_j, n ) = \gcd(x_ix_j, n ) = 1$，那么在此可以有 $x_i \circ x_j \in \{x_1, x_2, \ldots, x_{\varphi(n)}\}$。所以这个代数系统封闭。 - 结合性：
式子 $\forall x_i,x_j,x_k \in \{x_1, x_2, \ldots, x_{\varphi(n)}\}, x_i \circ x_j \circ x_k = x_j \circ x_i \circ x_k = x_j \circ (x_i \circ x_k)$ 是成立的。所以这也是满足的。同时还能说明可交换。 - 存在单位元：
$1$ 与完系中的任何数互质且是每个缩系中一定存在的元素。在施加运算后保持其它数不变，所以这一代数系统中有单位元。 - 存在逆元：
在缩系中，由于 $\forall x_i \in \{x_1, x_2, \ldots, x_{\varphi(n)}\}, \gcd(x_i, n) = 1 \Rightarrow ax_i + bn = 1 \Rightarrow ax_i \equiv 1 \pmod n \Rightarrow a\circ x_i = 1$。所以存在逆元。
由此我们证明了模 $n$ 缩剩余系关于乘法模 $n$ 构成阿贝尔群 $\mathbb{Z}^{\times}_n$。
所以 $a^{\varphi(n)} \equiv 1 \pmod n$ 在 $a \in \{x_1, x_2, \ldots, x_{\varphi(n)}\}$ 时是成立的。
正好说明了 $\varphi(n)$ 是该阿贝尔群的阶。从而能证明 $a^{k\varphi(n)} \equiv 1 \pmod {n}, k \in \mathbb{Z}$。
解密过程证明
求证：$\boxed{x \equiv x^{\lambda \varphi(n) + 1} \pmod{n} , \lambda \in \mathbb{Z}}$。
首先考虑 $x, n$ 互质的情况。我们已经证明了当 $a \in \{x_1, x_2, \ldots, x_{\varphi(n)}\}$ 时，$a^{k\varphi(n)} \equiv 1 \pmod {n}, k \in \mathbb{Z}$ 成立。
所以当 $\lambda \in \mathbb{Z}$ 时，$x^{\lambda \varphi(n)}\cdot x \equiv 1 \cdot x\equiv x \pmod{n}$。
再考虑 $x, n$ 不互质的情况。
首先要 注意到 $n$ 是由两个质数构造过来 的。如果 $x, n$ 不互质，则说明 $x$ 是 $p$ 或者 $q$ 或者 $n$ 的倍数。不妨记为 $x = sp, s \in \mathbb{Z}$。
我们可以很 tricky 地将 $x^{\lambda \varphi(n)}$ 转化到研究 $x^{\lambda \varphi(p)\varphi(q)}$ 上。
- 如果 $q$ 也是 $s$ 的因子，那么这会导致 $\gcd(x, n) = n$，从而直接有 $x \equiv 0 \pmod n$，那么相应地不管怎么算，都有 $x \equiv x^{\lambda \varphi(n) + 1} \equiv 0 \pmod n$。虽然对是对但是数字上不是很好，这启示我们 $x$ 需要小于 $n$。
- 如果 $s$ 中不含有 $q$，那么观察到 $\gcd(sp, q) = \gcd(p, q) = 1$，从而 $x = sp$ 也在模 $q$ 的缩系中。
- 那么直接有 $\Big(x^{\lambda \varphi(p)}\Big)^{\varphi(q)} \equiv x^{\lambda \varphi(p)\varphi(q)} \equiv 1 \pmod q$。
- 因此，$ x^{\lambda \varphi(n)} = iq + 1, i \in \mathbb{Z} \Rightarrow px^{\lambda \varphi(n)} = ipq + p = in + p \Rightarrow px^{\lambda \varphi(n)} \equiv p \pmod n$。所以得到 $x^{\lambda \varphi(n)} \equiv 1 \pmod n$。
因此这里也证明完了。
综合上述，求证得证。
针对这一加密算法的攻击
晚点再结合实例进一步补充自己的理解。
TODO: 前面的区域以后再来探索吧~
