密码与信任

辗转相除求最大公约数算法

欧几里得约前325–约前265《辗转相除法》

《原本》第七卷头两个命题。它是已知最早的非平凡算法，而且至今没有被更好的通用方法取代；它的扩展形式正是今天 RSA 里求私钥的那一步。

不试除，只隔步点名：把合数筛掉算法

埃拉托色尼约前276–约前194《筛子：让合数一个个漏下去》

名字是他起的，做法靠三百多年后尼科马库斯的《算术入门》传下来。生成 RSA 密钥时要找两个上千位的素数：随机取奇数，先拿一批小素数筛掉带小因子的，剩下的才去做概率素性检验——大多数候选数在这一步就被筛掉了。

p 是素数时，a 的 p 次方与 a 同余结构

费马1607–1665《费马小定理》

写在给弗雷尼克勒的一封信里，照例没给证明。今天它有两个用处：判一个大数是不是素数（费马素性检验），以及 RSA 正确性的基石。

模不是素数时也成立的那个版本结构

欧拉1707–1783《欧拉定理与 φ 函数》

φ(n) 数的是小于 n 且与 n 互素的整数有多少个。RSA 的公钥与私钥互为模 φ(n) 的逆元——这一整套就架在欧拉这条推广上。

同余：一套只看余数的算术语言

高斯1777–1855《《算术研究》与同余》

≡ 这个记号是他造的。在他之前，关于余数的结论散落在各处；有了同余的写法，它们才成为一门可以推演的学问。

元素个数有限的四则运算体系结构

伽罗瓦1811–1832《有限域：每一个二维码里都有他》

他二十岁上写下有限域时，想的是五次方程。一百三十年后，纠错码和分组密码发现自己需要的正是「一套有限的、封闭的、除法也做得通的算术」——而世上只有他构造的那一种。

分圆整数按一个素数拆成几块结构

库默尔1810–1893《一个不在场的因子，用同余去认它》

把 α 换成模 p 的一个单位根，一个分圆整数就被「照」成一个余数；p 有几个这样的根，就拆成几块，每一块各算各的。他做的是 λ 为素数的情形，并由此认出了那些不在场的理想因子。今天的后量子密码标准 ML-KEM（2024）算的正是这种数系：模 3329 的 x²⁵⁶ + 1 分圆环，快速乘法就是按 128 个模 3329 的单位根把它拆成 128 块二次的小环再乘——3329 − 1 恰好是 256 的 13 倍。

一个多项式什么时候只是把余数换了个次序结构

埃尔米特1822–1901《七个字母的换位，写成一个多项式》

加密要解得回来，那一步运算就必须是一次换位：不同的明文不能落到同一个密文上。模一个数取 e 次方正是这样一个多项式，它是不是换位，要看 e 与模的结构；他给的判据是一般的——各次幂之和全 ≡ 0，这个多项式就恰好把余数换了个次序。1896 年迪克森把它推广到任意有限域，今天叫置换多项式。AES（2001）那张 256 格的字节代换表，核心就是 256 元有限域上 x 的 254 次方，也就是求逆——一个置换多项式。

小于 x 的素数有多少不确定

阿达马1865–1963《σ = 1 上，一个零点也没有》

素数定理：小于 x 的素数个数与 x/ln x 之比趋于 1。他与德拉瓦莱普桑同年各自独立证出，两人的手法完全不同，而重量都压在同一句上——ζ 在 σ = 1 那条线上没有零点。这一条落到密码上是一笔很实在的账：随机取一个 1024 位的奇数，它是素数的概率约是 2/ln(2^1024)，约合三百五十五分之一，所以每凑出一个这样的素数，平均要试三百多个奇数。密钥生成要花多久，估的就是这条定理。

格里最短的向量有多短：只看体积就有上界边界

闵可夫斯基1864–1909《面积够 4，就罩得住一个格点》

凸体定理说：一个对称的凸体体积够大，就一定罩住一个非零格点，于是任何一张格里最短的那个向量，长度都有一个只看体积与维数的上界。上界给得出，找却难：维数升到几百，谁也不知道怎样快速找到那个最短向量。抗量子的格密码押的就是这件事——2024 年定为标准的 ML-KEM 与 ML-DSA，安全性都落在「高维的格里最短向量难找」上，而参数怎么取，第一步就是拿他的这条上界去估。