从欧拉定理到RSA算法：非对称加密的数学原理（二）
欧拉定理的变形与模反元素
引言
在上一篇中，我们系统梳理了同余、互质、欧拉函数等数论基础，并引出了欧拉定理：若正整数 $a$ 与 $n$ 互质，则 $a^{\varphi(n)} \equiv 1 \pmod{n}$。这一定理揭示了模运算下指数运算的周期性，是数论中最优美的结论之一。
然而，欧拉定理本身只是一个”静态”的结论——它告诉我们指数走到 $\varphi(n)$ 时会归一。但 RSA 算法所需要的是一个”动态”的工具：我们需要找到一个办法，让一个数被加密后再被还原。本篇将围绕这一目标，讨论欧拉定理的两个关键变形：指数的还原性质与模反元素。这两个变形是从欧拉定理走向 RSA 算法的必经桥梁。
一、变形一：指数的还原性质
1.1 从”归一”到”还原”
欧拉定理告诉我们：
$$a^{\varphi(n)} \equiv 1 \pmod{n}$$
这相当于说，在模 $n$ 的世界里，把一个与 $n$ 互质的数 $a$ 自乘 $\varphi(n)$ 次，就”走完了一圈”，回到了 1。那么，如果我们在指数上”再多走一步”，会发生什么？
将欧拉定理两端同时取 $k$ 次方（$k$ 为任意正整数）：
$$\left(a^{\varphi(n)}\right)^k \equiv 1^k \pmod{n}$$
即：
$$a^{k \cdot \varphi(n)} \equiv 1 \pmod{n}$$
两端再同乘以 $a$：
$$a^{k \cdot \varphi(n) + 1} \equiv a \pmod{n}$$
这就是欧拉定理的第一个关键变形。
1.2 变形的深刻含义
这个变形虽然只是简单的代数操作，但它的含义却极为深远：
如果一个数的指数可以写成 $k \cdot \varphi(n) + 1$ 的形式，那么对该数做这个指数次方的模 $n$ 运算，结果会还原为原数本身。
用符号表示就是：
$$a^{k \cdot \varphi(n) + 1} \equiv a \pmod{n}$$
换言之，指数 $k \cdot \varphi(n) + 1$ 就像是模运算世界里的”恒等操作”——无论输入什么，输出都是它自己。
1.3 一个具体例子
取 $a = 3$，$n = 10$，则 $\varphi(10) = 4$。
取 $k = 2$，则 $k \cdot \varphi(n) + 1 = 2 \times 4 + 1 = 9$。
验证：
$$3^9 = 19683$$
$$19683 \div 10 = 1968 \text{ 余 } 3$$
即 $3^9 \equiv 3 \pmod{10}$，确实还原了原数。
1.4 为什么这个变形对 RSA 至关重要？
RSA 的加密与解密过程可以形式化地表示为：
- 加密：$c \equiv m^e \pmod{n}$
- 解密：$m \equiv c^d \pmod{n}$
将加密结果代入解密公式：
$$c^d \equiv (m^e)^d \equiv m^{ed} \pmod{n}$$
如果 $ed$ 恰好等于 $k \cdot \varphi(n) + 1$，那么根据我们刚才推出的变形：
$$m^{ed} = m^{k \cdot \varphi(n) + 1} \equiv m \pmod{n}$$
明文被完美还原！
这就意味着，RSA 加解密的正确性，本质上就是欧拉定理这一变形的直接应用。而要让 $ed = k \cdot \varphi(n) + 1$ 成立，我们需要一个工具来”配对” $e$ 和 $d$——这个工具就是模反元素。
二、变形二：费马小定理——欧拉定理的特例
在讨论模反元素之前，我们先来看欧拉定理的另一个重要变形——费马小定理。
2.1 从欧拉定理到费马小定理
欧拉定理中，若模数 $n$ 恰好是一个质数 $p$，则根据欧拉函数的性质 $\varphi(p) = p - 1$，代入欧拉定理可得：
$$a^{p-1} \equiv 1 \pmod{p}$$
其中 $a$ 与 $p$ 互质（即 $p \nmid a$）。这就是著名的费马小定理（Fermat’s Little Theorem），它比欧拉定理早出现近一百年，可以视为欧拉定理在模数为质数时的特殊情形。
2.2 费马小定理的意义
费马小定理在密码学中有两大用途：
- 素性测试的基础：费马素性测试正是基于费马小定理的逆命题（虽然逆命题并不严格成立，存在 Carmichael 数等伪素数，但在工程上结合多次测试可以有效判断素数）。
- 理解欧拉定理的窗口：费马小定理的形式 $a^{p-1} \equiv 1 \pmod{p}$ 更为简洁，有助于我们直观理解”指数周期性”这一核心思想。
2.3 示例
取 $a = 3$，$p = 7$（7 是质数），验证费马小定理：
$$3^{7-1} = 3^6 = 729 = 104 \times 7 + 1$$
即 $3^6 \equiv 1 \pmod{7}$，符合费马小定理。
三、模反元素
3.1 定义
有了前两节的铺垫，我们现在可以引入本篇的核心概念——模反元素（Modular Multiplicative Inverse）。
定义：如果两个正整数 $a$ 和 $n$ 互质，那么一定可以找到整数 $b$，使得 $ab - 1$ 被 $n$ 整除，或者说 $ab$ 被 $n$ 除的余数是 1。这时，$b$ 就叫做 $a$ 对模 $n$ 的”模反元素”。
用同余式表示：
$$ab \equiv 1 \pmod{n}$$
3.2 直观理解：模运算中的”倒数”
在普通算术中，一个数 $a$ 的倒数 $a^{-1}$ 满足 $a \times a^{-1} = 1$。模反元素就是这一概念在模运算中的推广：在模 $n$ 的世界里，$a$ 的”倒数” $b$ 满足 $a \times b \equiv 1 \pmod{n}$。
例如，3 和 11 互质，3 的模反元素是 4，因为 $(3 \times 4) - 1 = 11$ 可以被 11 整除。
3.3 模反元素的存在性：欧拉定理的证明
模反元素为什么一定存在？欧拉定理给出了优雅的证明。
已知 $a$ 与 $n$ 互质，根据欧拉定理：
$$a^{\varphi(n)} \equiv 1 \pmod{n}$$
将左端拆分：
$$a \times a^{\varphi(n) - 1} \equiv 1 \pmod{n}$$
对照模反元素的定义 $ab \equiv 1 \pmod{n}$，我们立即得到：
$$b = a^{\varphi(n) - 1}$$
也就是说，$a$ 的 $\varphi(n) - 1$ 次方就是 $a$ 对模 $n$ 的一个模反元素。
这就从理论上证明了：只要 $a$ 与 $n$ 互质，模反元素必然存在。
3.4 模反元素的不唯一性
模反元素并不唯一。如果 $b$ 是 $a$ 的模反元素，那么 $b + kn$（$k$ 为任意整数）也都是 $a$ 的模反元素。
以 $a = 3$，$n = 11$ 为例，$b = 4$ 是一个模反元素。则：
$${\ldots, -18, -7, 4, 15, 26, \ldots}$$
这些数都是 3 对模 11 的模反元素。
在实际应用中，我们通常取最小的正整数解。
3.5 模反元素的求解：扩展欧几里得算法
虽然理论上 $b = a^{\varphi(n)-1}$ 是一个模反元素，但当 $\varphi(n)$ 很大时，直接计算幂次并不高效。更实用的方法是扩展欧几里得算法（Extended Euclidean Algorithm）。
根据模反元素的定义 $ab \equiv 1 \pmod{n}$，等价于：
$$ab - 1 = kn$$
即：
$$ab - kn = 1$$
令 $y = -k$，则问题转化为求解二元一次不定方程：
$$ax + ny = 1$$
根据数论中的结论，这个方程有整数解的充分必要条件是 $\gcd(a, n) = 1$。而扩展欧几里得算法正是求解这类方程的经典方法，它不仅能算出最大公约数，还能顺便给出一组整数解 $(x, y)$。
3.6 一个完整示例
以求 $e = 17$ 对 $\varphi(n) = 3120$ 的模反元素 $d$ 为例（这正是 RSA 经典教程中的参数）：
我们需要求解：
$$17d \equiv 1 \pmod{3120}$$
即：
$$17d - 3120k = 1$$
利用扩展欧几里得算法，可以得到一组整数解 $(d, k) = (2753, -15)$。
验证：
$$17 \times 2753 = 46801 = 15 \times 3120 + 1$$
确实满足 $17 \times 2753 \equiv 1 \pmod{3120}$。
因此，$d = 2753$ 就是 17 对模 3120 的模反元素（取最小正整数解）。
四、从变形到 RSA：关键拼图的完成
让我们把本篇的两个变形串联起来，看看它们如何共同为 RSA 算法搭建舞台。
4.1 两个变形的协同
- 变形一告诉我们：若 $ed = k \cdot \varphi(n) + 1$，则 $m^{ed} \equiv m \pmod{n}$，即加密后可以完美还原。
- 模反元素告诉我们：给定 $e$ 和 $\varphi(n)$（互质），一定存在 $d$ 使得 $ed \equiv 1 \pmod{\varphi(n)}$，即 $ed = k \cdot \varphi(n) + 1$。
两个变形合在一起，就构成了 RSA 的数学引擎：
- 选定公钥指数 $e$；
- 通过模反元素求出私钥指数 $d$；
- $e$ 和 $d$ 的乘积恰好满足 $ed = k \cdot \varphi(n) + 1$；
- 于是加密 $c = m^e \bmod n$ 与解密 $m = c^d \bmod n$ 构成一对可逆操作。
4.2 安全性的来源
这套机制之所以安全，关键在于：
- 公开的是 $n$ 和 $e$；
- 秘密的是 $d$、$p$、$q$、$\varphi(n)$；
- 要从 $e$ 求 $d$，必须知道 $\varphi(n)$；
- 要知道 $\varphi(n)$，必须分解 $n = p \times q$；
- 而大整数分解在计算上极其困难。
这就是 RSA 安全性的数学根基——正向计算容易，逆向推导不可行，即所谓的”陷门函数”（Trapdoor Function）。
五、小结
在本篇中，我们从欧拉定理出发，推导出两个关键变形：
- 指数的还原性质：$a^{k\varphi(n)+1} \equiv a \pmod{n}$，保证了”加密—解密”这一对操作的可逆性。
- 模反元素：$ab \equiv 1 \pmod{n}$，提供了配对公钥指数 $e$ 与私钥指数 $d$ 的数学工具。
此外，我们还介绍了费马小定理作为欧拉定理的特例，以及利用扩展欧几里得算法求解模反元素的实用方法。
至此，从欧拉定理到 RSA 算法的所有数学工具均已备齐。在下一篇中，我们将把这些工具组装起来，完整呈现 RSA 算法的密钥生成、加密与解密过程，并通过具体数字验证其正确性。
下一篇预告：《从欧拉定理到RSA算法（三）：RSA算法的完整构造与实例验证》