元数据卡
- 前置知识：第6章 组合数学
- 预计时间：45 分钟
- 核心难度：进阶
- 完成标志：理解模运算、欧几里得算法、中国剩余定理的基本思想
你的进度
组合塔的最高层。墙上的数字很特别——它们绕着一个圆圈走。"时钟里，11 点加 2 小时等于 1 点。那不是错误，是模算术。"馆长说。
你的任务
整数是计算机最基本的对象，但你每天在代码中做的整数加减乘除，其数学底层远比"小学算术"丰富。为什么哈希表用模运算做索引？RSA 加密的数学原理是什么？为什么有些数字叫做"素数"？这一章让你看清整数世界的底层结构。
本章分层
- 必读：整除与素数，模运算，最大公约数与欧几里得算法
- 选读：中国剩余定理，欧拉定理
破局 · 溯源
你在用 hashCode() % tableSize 做哈希槽定位。同事告诉你用 2 的幂作为 tableSize 会导致哈希碰撞更频繁。你觉得他在玄学，但测试数据确实支持了他的说法——用质数做模数时冲突更少。为什么？这是数论的问题。
整除与模：a ≡ b (mod m) 表示 a 和 b 除以 m 的余数相同。
模运算的性质和普通算术惊人地一致：
- (a + b) mod m = ((a mod m) + (b mod m)) mod m
- (a × b) mod m = ((a mod m) × (b mod m)) mod m
- a^b mod m 可以高效计算（快速幂算法）
第一条性质解释了为什么哈希表用模运算：你可以把任意大的 hashCode 映射到固定范围的槽位。
哈希表大小选质数的理由：如果 m 有因子 d，那么 key 分布在某些模 d 余数类上就不均匀。质数 m 只有 1 和 m 本身作为因子，所以能最大化分布的均匀性。
欧几里得算法：求 gcd(a, b)——最大公约数。
gcd(a, b):
while b ≠ 0:
a, b = b, a % b
return a这个算法高效且优雅——它是数学中最古老的算法之一（公元前 300 年），至今在密码学中活跃。
扩展欧几里得算法：不仅能求 gcd，还能给出整数 x, y 使得 ax + by = gcd(a, b)。这看起来像纯数学，但它是 RSA 加密中计算私钥的核心步骤。
素数：大于 1 且只能被 1 和自身整除的整数。
- 质因数分解定理：每个大于 1 的整数可以唯一分解为质数的乘积。
- 判断一个数是否为素数的朴素方法是试除到 √n。
- 对于大素数检测，Miller-Rabin 测试使用概率方法，是现代密码学的基石。
中国剩余定理：如果模数两两互质，一组同余方程有唯一解模这些模数的乘积。它在 RSA 加速计算、大整数运算中有实际应用。一个简化场景：你知道一个数除以 3 余 2，除以 5 余 3，除以 7 余 2——你能唯一确定这个数模 105 的值。
常见陷阱
- 混淆模运算中的负数。在数学中 -1 mod 5 = 4（因为 -1 + 5 = 4）。但在 C/Java 中，
-1 % 5得到 -1。这会导致涉及负数的哈希函数实现错误。 - 认为大整数分解很难是"当然的"。它不是——它是数论中一个未解决的重大猜想。RSA 的安全性依赖于"大整数分解困难"这个假设，如果被证伪整个体系需要重来。
- 在需要负数模运算的场景直接用取模符号。建议用
((x % m) + m) % m确保结果为非负。
通关挑战
- 用欧几里得算法计算 gcd(123456, 789012)。
- 编写一个快速幂算法计算 a^b mod m（Python）。验证当 m 为质数时，费马小定理 a^(m-1) ≡ 1 (mod m) 是否成立。
- 解释为什么哈希表大小为 2^n 时，低位相同的 key 会发生更多碰撞（提示：a mod 2^n 只依赖二进制低 n 位）。
旅人笔记
数论让整数世界透明了很多。模运算映射大象到固定范围，欧几里得算法求公约数，素数则撑起了整个加密世界的基石。
→ 下一站预告：你离开了组合塔。通向第三座塔——应用塔。在那里，数字不再只是整数和离散的计数，它们变成了向量、函数和连续的流动。