计算 $\phi(10)$ ：
1 到 10 之间，与 10 互质的数有：1, 3, 7, 9。一共 4 个。
所以， $\phi(10) = 4$ 。
计算素数的欧拉函数：
假设 $n$ 是一个素数（比如 $p=7$ ）。因为 7 是素数，所以比它小的所有正整数 (1, 2, 3, 4, 5, 6) 都和它互质。
规律 1：如果 $p$ 是素数，那么 $\phi(p) = p - 1$ 。
计算两个素数乘积的欧拉函数：
如果 $n$ 是由两个不同的素数 $p$ 和 $q$ 相乘得到的（即 $n = p \times q$ ）。欧拉函数有一个奇妙的乘法性质： $\phi(p \times q) = \phi(p) \times \phi(q)$ 。
规律 2：如果 $n = p \times q$ （ $p, q$ 为素数），那么 $\phi(n) = (p - 1)(q - 1)$ 。

二进制模幂算法 (Binary Exponentiation)

从左到右的二进制模幂算法（Left-to-Right Binary Exponentiation）

int modexp(int m, int e_bits[], int e_bits_len, int n)
{
    int R, L;
    int k = 0;
    int s = 1;
    while (k < e_bits_len)
    {
        if (e_bits[k] == 1)
            R = (s * m) % n;
        else
            R = s;

        s = R * R % n;
        L = R;
        k++;
    }
    return L;
}

霍纳法则（Horner's Method）

霍纳法则（Horner's Method），在中国古代称为“秦九韶算法”，它的核心思想是通过不断提取公因式，将多项式转化为一层层的嵌套，从而消灭高次幂的计算。

假设我们要计算 $m^5 \pmod n$ 。

数字 $5$ 的二进制是 $101_2$ 。在代码中，数组 e_bits[] = {1, 0, 1}（从高位到低位）。

我们可以把 $5$ 用多项式展开：

5 = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0

那么 $m^5$ 可以改写为：

m^5 = m^{1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0}

为了方便计算，数学家提取公因式（这称为霍纳法则），将其变为一层层嵌套的形式：

m^5 = ((m^1)^2 \times m^0)^2 \times m^1

推导

必备工具：指数的两个黄金法则

在开始推导前，我们需要复习初中代数里关于指数的两个核心定律：

法则 1（加法变乘法）： $m^{a + b} = m^a \times m^b$
法则 2（乘法变平方）： $m^{a \times 2} = (m^a)^2$

第一步：对“指数”使用霍纳法则

我们先不看底数 $m$ ，单看指数 $5$ 的二进制展开：

E = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0

如果把它看作一个关于变量 $x$ （这里 $x=2$ ）的多项式： $ax^2 + bx + c$ 。

按照传统的计算方法，你需要先算 $x^2$ ，再乘 $a$ ，再加后面的项。这需要多次独立的乘法。

我们对指数 $E$ 进行提取公因式 $2$ 的操作：

前两项 $(1 \times 2^2 + 0 \times 2^1)$ 都有因子 $2$ ，我们把 $2$ 提出来：
$E = (1 \times 2 + 0) \times 2^1 + 1 \times 2^0$
为了格式统一，我们把 $2^0$ 直接写成 $1$ （因为它就是末位数字），此时指数变成了：
$E = (1 \times 2 + 0) \times 2 + 1$

第二步：将指数放回底数 $m$ 上

现在，我们把经过霍纳法则变形的指数，放回到 $m$ 的右上角：

m^5 = m^{(1 \times 2 + 0) \times 2 + 1}

第一层拆解（处理最外面的 + 1）：

根据法则 1 ( $m^{a + b} = m^a \times m^b$ )，把尾巴上的 + 1 拆下来：

m^{(1 \times 2 + 0) \times 2 + 1} = m^{(1 \times 2 + 0) \times 2} \times m^1

第二层拆解（处理最外面的 x 2）：

根据法则 2 ( $m^{a \times 2} = (m^a)^2$ )，把乘 $2$ 变成外面的平方：

m^{(1 \times 2 + 0) \times 2} \times m^1 = (m^{(1 \times 2 + 0)})^2 \times m^1

第三层拆解（处理括号里的 + 0）：

再次使用法则 1：

(m^{1 \times 2 + 0})^2 \times m^1 = (m^{1 \times 2} \times m^0)^2 \times m^1

第四层拆解（处理最内层的 x 2）：

再次使用法则 2：

((m^1)^2 \times m^0)^2 \times m^1

代码逻辑计算（假设 $s$ 初始为 1）：

第 1 轮 ( $k=0$ , bit=1)：最内层
- R = (s * m) % n $\rightarrow$ 此时 $R = m^1$ 。
- s = R * R % n $\rightarrow$ 为下一轮做准备，将当前结果平方， $s = (m^1)^2 = m^2$ 。
- L = R $\rightarrow$ $L = m^1$ 。
第 2 轮 ( $k=1$ , bit=0)：中间层
- 由于 bit 为 0，不乘 $m$ 。
- R = s $\rightarrow$ 直接继承上一轮的平方结果， $R = m^2$ 。
- s = R * R % n $\rightarrow$ 继续为下一轮平方， $s = (m^2)^2 = m^4$ 。
- L = R $\rightarrow$ $L = m^2$ 。
第 3 轮 ( $k=2$ , bit=1)：最外层
- R = (s * m) % n $\rightarrow$ $R = m^4 \times m^1 = m^5$ 。
- s = R * R % n $\rightarrow$ 算出 $m^{10}$ （由于循环结束，这个值被废弃）。
- L = R $\rightarrow$ 最终结果 $L = m^5$ 。

代码中的 s = R * R 负责将当前的指数“左移”（即翻倍），而 if (e_bits[k] == 1) 负责在末尾加上个位数。这使得原本需要乘 $e$ 次的运算，变成了只需乘 $\log_2(e)$ 次。

RSA 算法

密钥生成

在加密之前，我们需要生成一对钥匙：公钥（公开给所有人用来加密）和私钥（自己藏好用来解密）。

第一步：寻找素数
随机选择两个不相等的巨大素数 $p$ 和 $q$ 。
第二步：计算公共模数 $n$
$n = p \times q$
这个 $n$ 的长度就是密钥长度（比如2048位）。 $n$ 是公开的。
第三步：计算欧拉函数 $\phi(n)$
根据欧拉函数性质，因为 $p$ 和 $q$ 都是素数：
$\phi(n) = (p-1)(q-1)$
$\phi(n)$ 代表在小于等于 $n$ 的正整数中，与 $n$ 互质的数的个数。这个值必须严格保密。
第四步：选择公钥指数 $e$
随机选择一个整数 $e$ ，条件是 $1 < e < \phi(n)$ ，且 $e$ 与 $\phi(n)$ 互质。通常会选择 65537。
此时，公钥诞生了： $(e, n)$
第五步：计算私钥指数 $d$
找到一个整数 $d$ ，使得 $e$ 和 $d$ 相乘后对 $\phi(n)$ 取模余数为 1。即求 $e$ 在模 $\phi(n)$ 下的乘法逆元：
$e \times d \equiv 1 \pmod{\phi(n)}$
这等价于 $e \times d = k \times \phi(n) + 1$ （ $k$ 为正整数）。
此时，私钥诞生了： $(d, n)$

数据加密与还原

假设我们要发送一条机密信息，首先我们将其转换为一个数字 $m$ （必须满足 $m < n$ ）。

加密过程（使用公钥）

发送方使用接收方的公钥 $(e, n)$ ，计算密文 $c$ ：

c \equiv m^e \pmod{n}

发送方将计算出的数字 $c$ 发送出去。

解密/还原过程（使用私钥）

接收方收到密文 $c$ 后，使用自己的私钥 $(d, n)$ 进行计算，就能神奇地还原出 $m$ ：

m \equiv c^d \pmod{n}

我们将加密公式代入解密公式：

c^d \equiv (m^e)^d \equiv m^{ed} \pmod{n}

我们在生成密钥的第五步知道： $ed = k\phi(n) + 1$ 。所以：

m^{ed} = m^{k\phi(n) + 1} = m^{k\phi(n)} \times m = (m^{\phi(n)})^k \times m

根据欧拉定理：如果 $m$ 和 $n$ 互质，那么 $m^{\phi(n)} \equiv 1 \pmod{n}$ 。

因此：

(m^{\phi(n)})^k \times m \equiv 1^k \times m \equiv m \pmod{n}