1.4 初等数论与整除：密码学的地基
1.4 初等数论与整除：密码学的地基
初等数论研究整数的整除结构：素数、最大公约数、同余与模运算。本节手工执行欧几里得算法，理解算术基本定理，再看一眼这些两千年前的知识如何变成今天网上银行的地基。这是第一章主线（数系扩张）的旁支：不向外扩张，向内挖掘整数自身的结构。
为什么"除得尽除不尽"值钱
前面三节一直在扩张数系，让"除不尽"不再是问题。这一节反其道而行：恰恰研究除不尽的时候，余数是多少。钟表只有 12 个刻度，第 25 小时指向 1；今天是星期三，100 天后是星期几——这些都是"只关心余数"的算术。而整个现代密码学的底牌是：把两个大素数相乘，计算机一瞬间；反过来把乘积分解回两个素数，天荒地老。这个不对称性，全部建立在初等数论之上。
欧几里得算法：最古老也最高效的算法之一
求最大公约数，中学的短除法对大数很慢。欧几里得在两千三百年前给出的算法基于一个观察：a 与 b 的最大公约数，等于 b 与 a 除以 b 的余数的最大公约数。
手算 gcd(252, 198)：
- 252 = 1 × 198 + 54 （转为求 gcd(198, 54)）
- 198 = 3 × 54 + 36 （转为求 gcd(54, 36)）
- 54 = 1 × 36 + 18 （转为求 gcd(36, 18)）
- 36 = 2 × 18 + 0 （余数为零，答案就是 18）
四步收工。为什么成立？任何整除 198 与 54 的数，也整除 198 加上若干倍的 54（即 252）；反过来任何整除 252 与 198 的数也整除它们的差。每一步丢掉的只是"公倍数的包装纸"，公约数原封不动地传递到最后。
>>> def gcd(a, b): ... while b: ... a, b = b, a % b ... return a >>> gcd(252, 198) 18 >>> gcd(1234567890, 987654321) # 大数也只要寥寥几步 9
两行循环就是全部实现。这个算法的步数与数字的位数成正比（而非与数值大小成正比），所以两百位的数也只是几百步——快得惊人。
贝祖等式是它的副产品：存在整数 x、y 使 ax + by = gcd(a,b)。往回代入手算：18 = 54 - 36；36 = 198 - 3×54；54 = 252 - 198。整理得 18 = 4×252 - 5×198。验证：1008 - 990 = 18，成立。
>>> from math import gcd >>> from sympy import igcdex >>> gcd(252, 198) 18 >>> x, y, g = igcdex(252, 198) >>> x, y, g (4, -5, 18) >>> 252*4 + 198*(-5) 18
SymPy 的 igcdex 给出同样的 x=4、y=-5——手算反推与算法输出完全一致。
算术基本定理：素数是整数的字母表
素数是大于 1 且只有 1 和自身两个因数的整数。算术基本定理说：任何大于 1 的整数唯一地分解为素数的乘积（不计顺序）。84 = 2×2×3×7，不管你怎么拆，素因子和次数都一样。素数之于整数，正如字母之于单词——有限的原件，无限的组合。
判定素数最朴素的办法是试除：用 2 到根号 n 之间的整数逐个去除。
>>> def is_prime(n): ... if n < 2: return False ... for d in range(2, int(n**0.5) + 1): ... if n % d == 0: ... return False ... return True >>> [n for n in range(2, 50) if is_prime(n)] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
试除到根号就够，因为若 n 有大于根号 n 的因数，必伴随一个小于根号 n 的因数——因数成双成对出现。
同余与模运算：钟表算术
记 a 与 b 模 n 同余为 a ≡ b (mod n)，意思是 a 和 b 除以 n 余数相同。三条基本性质（对加、减、乘封闭）：
- 若 a ≡ b，c ≡ d (mod n)，则 a+c ≡ b+d (mod n)；
- a-c ≡ b-d (mod n)；
- a×c ≡ b×d (mod n)。
这让"大数的余数"可以边算边取，不必先算出天文数字：算 3 的 100 次方模 7，只需把"乘 3 取余 7"重复一百次，中间结果永远不超过 7。
>>> pow(3, 100, 7) # 内置三参数 pow：模幂运算 4 >>> pow(91, 7, 29) # RSA 加密的核心原语：底数、指数、模 20
三参数 pow 正是 RSA 加解密每次做的运算——大素数 p、q 的乘积当模数，指数当密钥，安全性系于"外人分解不出 p 和 q"。
⚠️ 常见坑：同余对除法不封闭。6 ≡ 0 (mod 3)、3 ≡ 0 (mod 3)，但不能"约去公因子"去比较 2 与 1——模算术里消去律需要附加条件（模与消去的数互素）。
欧几里得算法的执行轨迹
同余的实战：星期几问题
今天是星期三，100 天后是星期几？100 除以 7 余 2（98 = 14×7），相当于"2 天后"，星期五。3 的 100 次方个位是几？个位只看模 10：3 的幂个位按 3、9、7、1 四位一循环，100 除以 4 余 0，落在循环末位，个位是 1。大数问题化成余数问题是同余思想的日常用法，密码学里的模指数运算是同一件事的超大杯版本。
常见问题
问：RSA 敢公开乘积，不怕别人分解出两个素数吗？
答：不是"不能"，是"太慢"。经典计算机上分解几百位的数没有快速算法；算力翻番，密钥再加几十位就重新拉开差距。
问：素数有无穷多个吗？
答：有，欧几里得的证明两千年未倒：假设素数有限，把它们全乘起来加 1，这个新数不被名单里任何素数整除——要么它是新素数，要么它的素因子不在名单里，矛盾。
本节要点回顾
- 欧几里得算法：gcd(a,b) = gcd(b, a mod b)，步数与位数成正比，两行代码实现；
- 贝祖等式 ax + by = gcd(a,b) 可由算法回代求出，手算与
igcdex互相印证； - 算术基本定理：素因子分解存在且唯一，素数是整数的字母表；
- 试除判素只需除到根号 n，因数成对出现是原因；
- 同余对加减乘封闭、对除法不封闭，三参数
pow是模幂的原语、RSA 的心脏。
第一章到此收官。数系的原料备齐，第二章开始操作符号：让未知数 x 登场。