第3章：数论基础——模运算、素数、循环群与离散对数
做联邦学习多方密钥协商，绕不开几个数论概念。它们就像地基里的钢筋，看不见但撑起整个安全体系。我当年刚接触密码学协议时，总觉得这些理论离工程很远，后来在写密钥交换模块时栽了几个跟头才明白：基础不牢，后面全是坑。
3.1 模运算：密码学的瑞士军刀
模运算说白了就是“取余数”。我给你一个数字，你除以一个固定数，只看余数。我们通常记作 a mod n。它最妙的地方是：所有结果都落在 [0, n-1] 这个有限集合里。这个“有限”在密码学里太重要了——你想想看，无限的东西怎么在计算机里精确表示？
核心性质：模运算满足加法、乘法封闭性，且存在单位元和逆元（当与模数互质时）。这些是构建循环群的前提。
| 运算 | 定义 | 密码学用途示例 |
|---|---|---|
| 模加 | (a + b) mod n | 一次性密码本、秘密共享 |
| 模乘 | (a * b) mod n | RSA、ElGamal 加密 |
| 模幂 | a^b mod n | Diffie-Hellman 密钥交换 |
| 模逆 | a * x ≡ 1 mod n | 欧几里得算法、密钥派生 |
我个人习惯在工程代码里把模运算用 pow(a, b, n) 代替 (a ** b) % n。前者避免大整数中间结果膨胀，后者在 Python 里能直接溢出——我线上就因为这个崩过一次。
3.2 素数性质：为什么密码学偏爱它们
素数就是除了1和自身以外没有其他因子的正整数。可为什么密码学非要用素数当模数？我来给你拆开说：
- 单位群最大：模素数
p下，所有非零元素都有乘法逆元，构成一个有限域。这意味着你可以随意做除法，不会出现“零因子”尴尬事。 - 离散对数难：素数阶循环群上的离散对数问题公认困难——这是所有密钥协商协议的安全根基。
- 结构简单：素数幂
p^k的群结构复杂，实际场景几乎只用p本身，省得处理多余子群。
避坑指南：我曾经在生产环境中误把合数当作大素数，导致密钥交换出现小阶子群攻击漏洞。从那以后，我每次选模数都会用 Miller-Rabin 做确定性筛，再跑一遍 Pocklington 验证。别信随机数生成器自动筛出来的素数，自己亲手验一遍才放心。
3.3 循环群：密钥协商的舞台
一个群如果所有元素都能由某个固定元素的幂生成，就叫循环群。这个固定元素叫生成元（generator）。比如模7下的乘法群 Z*_7 = {1,2,3,4,5,6}，用生成元3的幂次就能得到全部元素：3^1=3, 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1。
理解了生成元，Diffie-Hellman 就一目了然：双方各自选择私钥 a 和 b，交换 g^a mod p 和 g^b mod p，最后算出相同的共享密钥 g^(ab) mod p。联邦学习里，每个客户端和服务器之间的密钥协商本质上就是把这个过程扩展到多方。
3.4 离散对数问题：难在哪里？
给定 y = g^x mod p，已知 g、y 和 p，想求出 x——这就是离散对数问题。难度在于：没有比穷举或指数级算法更好的通用解法。你想想看，当 p 是2048位大素数，穷举比宇宙年龄还长。
注意：不是所有群上的 DLP 都同样困难。椭圆曲线群上的 DLP 比同等长度素数域上的 DLP 更难攻破。我们在联邦学习方案中可以根据安全等级灵活选择：普通场景用 2048 位模素数群，高安全或低带宽场景换椭圆曲线。
3.5 知识结构总览
下面这张图梳理了这些概念的关系。你可以看到：模运算提供基本框架，素数性质保证群的结构纯净，循环群定义生成元与幂运算，离散对数问题则把这一切转化为密码学安全承诺。我在设计联邦学习密钥协商原型时，就是按这个逻辑搭的代码模块。
从图上你能看到：模运算和素数共同支撑循环群；循环群定义生成元与离散对数问题；DLP 直接转化为密钥协商的安全性；最终落地到联邦学习场景。我在调优多方协议时曾反复回到这张图来排查问题——比如有一次发现群里出现了小阶子群，就是因为模数选成了合数。
如果你在实现中不确定生成元的选取，可以先用穷举法验证 g^((p-1)/q) ≠ 1 对所有 p-1 的大素因子 q 成立。这是安全生成元的必检条件，也是我所在团队内部代码审查的固定检查项。
3.6 工程选型要点
在实际联邦学习系统中，我总结过一张参数对照表，帮你快速做选择：
| 场景 | 推荐模数大小 | 素数类型 | 生成元条件 |
|---|---|---|---|
| 常规联邦学习（10-100客户端） | 2048 bit | 强素数（Sophie Germain） | g 的阶为 (p-1)/2 |
| 高频聚合（IoT设备） | 256 bit（ECC） | 椭圆曲线素数域 | 曲线生成元G |
| 长期存储密钥（合规审计） | 4096 bit | 安全素数 | g=2 或 5 且验证阶 |
最后提醒一句：模运算、素数、循环群、离散对数这四个概念，有一个地方没搞透，到后面协议设计就会漏洞百出。别嫌基础——我当年就是跳过循环群直接看 Diffie-Hellman，结果在写多方聚合时死活想不通为什么密钥空间会坍缩。老老实实回来补课，才把协议改对。