本科数学 · 数论基础：整数的秘密与 RSA

数论基础：整数的秘密与 RSA

Number Theory · 古代智力游戏，现代安全命根子

【章首引子】你刷手机支付，背后有几百位的大质数在替你站岗。两个大质数相乘只要一秒，把乘积拆回去却要算到天荒地老。RSA 加密就建立在这个"易乘难拆"的不对称上——古代数学家的纯智力游戏，成了互联网安全的命根子。

① 是什么：整除、同余、费马小定理

啥整数与模运算

质数：只能被 1 和自己整除（2,3,5,7,11…）。最大公约数 gcd：公共因子里最大的。欧几里得算法：gcd(a,b) = gcd(b, a mod b)，反复取余直到余数为 0。

同余：a ≡ b (mod n) 表示除以 n 余数相同。费马小定理：aᵖ ≡ a (mod p)（p 质数）。欧拉定理：a^φ(n) ≡ 1 (mod n)（a 与 n 互质），φ(n) 是欧拉函数。

② 怎么想到的

思解题心法

求 gcd 用辗转相除：gcd(a,b)=gcd(b,a mod b)，几行代码。

证数论基础：整数的秘密与 RSA的核心定理与公式

核心定理：①辗转相除法：$\gcd(a,b)=\gcd(b,\ a\bmod b)$，直到余数为 $0$。②裴蜀定理：存在整数 $x,y$ 使 $ax+by=\gcd(a,b)$（扩展欧几里得算法可求出来）。③费马小定理：$p$ 为素数且 $\gcd(a,p)=1$ 时，$a^{p-1}\equiv 1\pmod p$。④欧拉定理：$\gcd(a,n)=1$ 时 $a^{\varphi(n)}\equiv 1\pmod n$，其中 $\varphi$ 是欧拉函数。⑤RSA 构造：$n=pq$，$\varphi(n)=(p-1)(q-1)$，取 $e$ 与 $\varphi(n)$ 互素并解出 $d$ 使 $ed\equiv 1\pmod{\varphi(n)}$；加密 $c\equiv m^{e}\pmod n$，解密 $m\equiv c^{d}\pmod n$。

推导思路：①由 $ed\equiv 1\pmod{\varphi(n)}$ 的定义，存在整数 $k$ 使 $ed=1+k\,\varphi(n)$。②把密文代进去解密：$c^{d}\equiv(m^{e})^{d}=m^{ed}=m^{\,1+k\varphi(n)}=m\cdot\big(m^{\varphi(n)}\big)^{k}\pmod n$。③当 $\gcd(m,n)=1$ 时，由欧拉定理 $m^{\varphi(n)}\equiv 1\pmod n$，于是 $\big(m^{\varphi(n)}\big)^{k}\equiv 1$，故 $c^{d}\equiv m\pmod n$——密文真的还原成了原文。④若 $\gcd(m,n)\neq 1$，因 $n=pq$ 且 $0\leq m<n$，只可能是 $p\,|\,m$ 或 $q\,|\,m$；对两个素因子分别用费马小定理，再由中国剩余定理拼回来，结论仍然成立。

直觉把握：RSA 的安全性全押在"大整数分解很难"这件事上：把两个大素数乘起来小学算术就能做，可要把乘积拆回因数，目前没有多项式时间算法（量子计算机上的 Shor 算法除外）。AI/工程里，你每次访问 https、每次从模型仓库拉加密权重，背后都是它；此外哈希函数里的模运算、随机数发生器里的线性同余，也都是模算术的亲戚。

模运算就是取余：加减乘都可以先 mod 再算。

RSA 思想：正向乘出 n=pq 很快，反向分解 n 极难——公开 n（公钥），私钥藏在 p、q。

③ 完整解法：三个例题

例题1：gcd(48, 36)

【审题】辗转相除。

思路：反复取余。

逐步解法：gcd(48,36)=gcd(36,12)=gcd(12,0)=12。

例题2：费马小定理算 2¹⁰ mod 11

【审题】p=11 质数。

思路：2¹¹≡2 (mod 11)。

逐步解法：2¹⁰ ≡ 1 (mod 11)（费马小定理推论）。答案 = 1。不用真算 1024。

例题3：RSA 为什么安全

【审题】公钥 n=pq 公开。

思路：易乘难拆。

逐步解法：加密用 n，解密需要 p、q。乘出 n 秒级，分解几百位 n 在计算上不可行。这个不对称，让公开加密却只有私钥能解。

数论核心公式 $gcd(a,b) = gcd(b, a mod b)$ | 费马小定理 aᵖ ≡ a (mod p)（p 质数）
$\text{欧拉定理} a^\phi (n) ≡ 1 (mod n)(a\perp n)$ | RSA：$n=pq \text{公开}, \text{私钥藏} p\text{、}q$

④ 用途与案例

HTTPS 与区块链

RSA 公钥加密、数字签名——每次 https、每次区块链交易，都靠大整数分解难。

校验码

ISBN、信用卡号最后一位是模运算算出的校验位，输错一位机器立刻发现。

哈希函数

密码哈希、指纹、验证码，底层大量用模运算与数论性质。

编程基础

取余判整除、循环队列、随机数生成——日常代码里到处是 mod。

⑤ 延展

展知识衔接地图

往研究生走：初等数论 → 代数数论/椭圆曲线密码（ECC、格密码）。往算法走：量子计算机若成熟，Shor 算法能快速分解大整数——会颠覆 RSA，这是后量子密码的研究前沿。

思维陷阱

以为"分解大整数"迟早能暴力试出来。对几百位的 n，从 2 试到 √n 是天文数字，全世界计算机一起算也算不完。不是暂时没找到快速算法，而是问题本身计算上极不对称。

练习

【基础】gcd(48, 36) = ？

查看思路与解答

12。

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

【进阶】为什么 ISBN 最后一位能防错？

查看思路与解答

把前面数字按规则（如交替乘 1 和 3）求和再 mod 10，算出校验位。输错任意一位，校验和就对不上，机器立即报警。

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

费曼学习法：讲给别人听

① 用自己的话讲：整除、同余、素数是整数的语言；RSA 密码的底气就是"两个大素数乘起来容易、拆回去难"。

② 举个反例（什么条件下不成立）：同余式里不能随便约掉公因数（除非它和模数互素）；费马小定理的前提是 p 为素数，条件一丢就错。

③ 哪里还说不清：欧拉函数 φ(n) 到底怎么一步步算？

记

小结卡

① gcd 用辗转相除；费马小定理 aᵖ≡a (mod p)。

② 质数乘积"易乘难拆"= RSA 命根子；校验码用模运算防错。