🔢 mathematics

Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

本文通过分类卡迈克尔数并开发一种基于已有欧拉伪素数相乘的快速算法，成功构造出能经受住前 47 个素数底数（即直至 211 的所有整数底数）检验的欧拉伪素数，其中表现最佳者通过了 211 的测试。

原作者： Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

发布于 2026-02-26

📖 1 分钟阅读🧠 深度阅读

原作者： Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇文章讲述了一群数学家如何找到了一群极其“狡猾”的假数字，它们能骗过计算机最严格的“身份验证”测试，直到第 47 次测试才露出马脚。

为了让你轻松理解，我们可以把这篇论文想象成一场**“顶级伪装者大赛”**。

1. 背景：为什么我们需要“假数字”？

想象一下，你正在开一家银行（比如 RSA 加密系统），你需要大量的真金白银（质数）来建立金库。
但是，在茫茫数字海洋里找到真正的“质数”非常困难且耗时。所以，银行保安（计算机算法）通常会用一种快速安检门（比如 Solovay-Strassen 测试）来检查一个数字是不是质数。

真质数：无论保安怎么查，都永远通不过安检（因为它是真的）。
普通合数：大部分情况下，保安随便问几个问题（比如“你除以 2 余几？”），就能识破它是个假货。
伪质数（Pseudoprimes）：这是一群高明的骗子。它们不是质数，但面对保安的某些问题，它们能给出和真质数一模一样的回答，从而混进金库。

这篇论文的目标就是：找到那个最狡猾的骗子，让它能连续通过 47 次不同的保安提问，直到第 48 次才被抓。

2. 核心角色：卡迈克尔数（Carmichael Numbers）

在寻找骗子的过程中，作者发现了一个特殊的家族，叫卡迈克尔数。

比喻：想象这是一个**“全能伪装者家族”**。普通的骗子可能只能骗过保安问“你除以 2 余几？”，但卡迈克尔数家族成员，无论保安问什么（只要不直接问它的因子），它们都能完美回答，表现得像个真质数。
作者发现，在这个家族里，有一类成员特别擅长通过欧拉测试（一种更高级的安检）。

3. 分类学：给骗子贴标签

作者把这群卡迈克尔数分成了不同的“班级”（Class A, B1, B2），就像给特工分派不同的伪装等级：

A 班（Class A）：这是**“超级伪装者”**。在这个班级里，大约有一半的数字都能完美通过欧拉测试。这是作者最想要的“种子选手”。
B 班（Class B）：这些是“普通伪装者”，通过率较低，或者表现不稳定。

关键发现：作者发现，如果你把两个A 班的伪装者乘在一起，只要它们满足特定条件，生成的新数字依然是一个A 班的伪装者，而且它的伪装能力更强！

4. 制造超级骗子的“炼金术”

作者发明了一种**“乘法炼金术”**算法：

收集种子：先找到一些小的、能骗过前几个保安的 A 班卡迈克尔数。
配对融合：把两个能骗过同一个关卡（比如前 37 个质数）的数字乘起来。
筛选升级：
- 如果乘积依然满足“卡迈克尔数”的规则，并且依然属于"A 班”，那么恭喜你，你得到了一个更强的骗子。
- 这个新骗子不仅能骗过前 37 个保安，甚至能骗过第 38、39 个……直到第 47 个！

这就好比：

你有一个能骗过 10 个守卫的间谍。
你有另一个也能骗过 10 个守卫的间谍。
你们俩“合体”后，变成了一个能骗过 20 个守卫的超级间谍。
作者不断重复这个过程，像搭积木一样，把小骗子拼成大骗子。

5. 最终成果：211 号传奇

经过这种“乘法炼金术”，作者制造出了终极伪装者：

这个数字非常大（有 1230 位，写出来比《哈利·波特》全书还长）。
它面对前 47 个质数（2, 3, 5, ..., 211）作为“考官”时，全部通过了测试。
它完美地伪装成了质数，直到第 48 个考官（223）出现，才终于被识破。

这意味着什么？
在密码学领域，这提醒我们：如果我们只随机抽查几个数字来验证质数，可能会遇到这种“超级骗子”，导致加密系统被攻破。虽然概率极低，但理论上存在这种风险。

6. 有趣的插曲：索菲·热尔曼伪质数

在文章最后，作者还发现了一类特殊的“骗子”，叫索菲·热尔曼伪质数。

比喻：这就像是一对**“双胞胎刺客”**（两个特定的质数相乘）。它们虽然不如卡迈克尔数那么全能，但在特定条件下，也能骗过四分之一的测试。作者把它们列为“银牌得主”，并猜想它们可能是除了卡迈克尔数之外，唯一能骗过这么多测试的数字。

总结

这篇论文就像是一部**“数字伪装者进化史”**：

作者分析了骗子的基因（分类卡迈克尔数）。
发现了繁殖秘诀（将同类伪装者相乘）。
通过不断迭代升级，制造出了历史上最顽强的假质数，它能连续通过 47 次最严格的质数测试。

这不仅展示了数学的趣味性，也为未来的密码安全敲响了警钟：永远不要完全相信一个数字，除非你彻底检查过它的底细。

论文技术总结：OURS GOES TO 211: EULER PSEUDOPRIMES TO 47 PRIME BASES

1. 研究背景与问题 (Problem)

在公钥密码系统（如 RSA 和 Diffie-Hellman）中，生成大素数是核心步骤。通常通过随机采样并运行概率性素性测试（如 Solovay-Strassen 或 Miller-Rabin）来寻找素数。

核心问题：如果攻击者能够构造“伪素数”（Pseudoprimes），即合数但能通过素性测试的数，就能欺骗系统接受合数为素数，从而破坏安全性。
具体目标：本文专注于 Solovay-Strassen 测试。该测试基于欧拉准则：对于候选数 $n$ $n$ 和底数 $a$ $a$ ，检查是否满足 $\left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod n$ $(\frac{a}{n}) \equiv a^{(n - 1) /2} (mod n)$ 。
- 满足该等式的合数称为 欧拉伪素数 (Euler Pseudoprime)。
- 不满足的 $a$ 称为“欧拉见证者 (Euler witness)"。
挑战：Solovay-Strassen 测试的错误率上限为 $1/2$ （即最多有 $1/2$ 的底数可能是“欧拉骗子/Euler liar"）。作者旨在构造一个合数，使其能通过前 47 个连续素数底数（直到 211）的测试，即该数对前 47 个素数底数都是欧拉伪素数。

2. 方法论 (Methodology)

作者提出了一套系统的分类、筛选和构造算法，主要步骤如下：

2.1 基于卡迈克尔数 (Carmichael Numbers) 的筛选

理论基础：卡迈克尔数是对所有互质底数都满足费马小定理 $a^{n-1} \equiv 1 \pmod n$ 的合数。根据引理 5，任何欧拉伪素数底数也是费马伪素数底数，因此卡迈克尔数是寻找欧拉伪素数的最佳候选。
分类系统：作者利用卡迈克尔 $\lambda$ $λ$ 函数（ $\lambda(n)$ $λ (n)$ ）和指数 $i(n) = (n-1)/\lambda(n)$ $i (n) = (n - 1) / λ (n)$ 的奇偶性，将卡迈克尔数分为三类：
- Class A： $i(n)$ 为偶数。此类数拥有最大数量的欧拉骗子（ $\phi(n)/2$ ），且所有骗子的雅可比符号均为 1。
- Class B1： $i(n)$ 为奇数，且 $h < k$ （ $h$ 为具有最大 2-进估值 $v_2(p_i-1)$ 的素因子个数）。欧拉骗子数量为 $\phi(n)/2^{h+1}$ 。
- Class B2： $i(n)$ 为奇数，且 $h = k$ 。欧拉骗子数量为 $\phi(n)/2^{k-1}$ ，雅可比符号正负各半。
策略：由于 Class A 拥有最多的欧拉骗子（概率最高），算法主要聚焦于构造 Class A 的卡迈克尔数。

2.2 乘法构造算法 (Multiplication Algorithm)

作者发现，将两个已知能通过一定范围底数测试的欧拉伪素数相乘，往往能产生能通过更多底数测试的新伪素数。

原子卡迈克尔数：定义为不能分解为其他卡迈克尔数乘积的卡迈克尔数。
构造逻辑：
- 设 $n_1, n_2$ 均为 Class A 的卡迈克尔数，且都能通过底数 $a$ 的测试。
- 若 $n = n_1 n_2$ 也是 Class A 的卡迈克尔数，根据引理 13，它不仅能通过 $a$ ，还能通过 $a$ 之后的下一个素数底数。
- 关键条件：为了确保乘积仍为 Class A，需满足 $v_2(n_1-1)$ 和 $v_2(n_2-1)$ 的最小值大于 $\lambda(n)$ 的 2-进估值。
算法流程 (Algorithm 1)：
1. 输入两个 Class A 的欧拉伪素数 $n_1, n_2$ （来自同一底数集合 $epsp(a)$）。
2. 检查 $v_2(n_2-1) > v_2(\lambda(n_1))$ 等必要条件。
3. 检查互质性 ( $\gcd(n_1, n_2)=1$ ) 和卡迈克尔性质 ( $\lambda(n) | n-1$ )。
4. 若满足，计算新数的 $\lambda(n)$ 和 $v_2$ 属性，并测试其能通过多少个连续素数底数。
5. 利用对称性构造（如 $epsp_4[2]^2$ 表示两个 $epsp_2$ 的乘积），逐步构建更大的伪素数。

2.3 过滤与优化

小因子过滤：移除含有小素因子（如 $<150$ ）的数，因为如果底数 $a$ 是 $n$ 的因子，测试必然失败。
模 120 过滤：统计发现，高质量的欧拉伪素数绝大多数满足 $n \equiv 1 \pmod{120}$ 。利用此性质可大幅减少搜索空间。
对称构造：优先选择结构对称的乘积（如 $epsp_2 \times epsp_2$ ），以提高通过后续底数测试的概率。

3. 主要贡献 (Key Contributions)

卡迈克尔数的精细分类：提出了基于 $\lambda(n)$ 和 $i(n)$ 的 Class A/B 分类法，并证明了 Class A 拥有最大比例的欧拉骗子，为构造提供了理论指导。
高效的构造算法：开发了一种基于乘法迭代的算法，通过组合已知的高质量欧拉伪素数来生成更大的伪素数，而非盲目搜索。
记录保持者：构造出了一个能通过 前 47 个素数底数（即从 2 到 211）的欧拉伪素数。这是目前该领域的已知最佳记录。
发现新型伪素数：除了卡迈克尔数，还定义并分析了 Sophie Germinus 伪素数（形如 $p_1(2p_1-1)$ ，其中 $p_1, 2p_1-1$ 均为素数），这类数拥有 $\phi(n)/4$ 的欧拉骗子。

4. 实验结果 (Results)

最佳结果：
- 找到了一个 1230 位的合数，它是欧拉伪素数，能通过从 2 到 211 的所有 47 个连续素数底数的 Solovay-Strassen 测试。
- 该数属于 Class A 卡迈克尔数。
统计发现：
- 在生成的欧拉伪素数中，Class A 占据了绝对主导地位（例如在 $epsp_2(a)$ 中，Class A 占比极高，而 Class B2 几乎为零）。
- 随着构造层数的增加（从 $epsp_2$ 到 $epsp_{16}$ ），能通过的底数数量显著增加，但受限于素因子重复导致的非无平方因子（non-squarefree）问题，构造难度呈指数级上升。
- 大部分高质量伪素数满足 $n \equiv 1 \pmod{120}$ 。

5. 意义与影响 (Significance)

密码学安全性警示：该结果展示了在对抗性环境下（Adversarial conditions），如果攻击者能够控制素性测试的输入或拥有构造伪素数的能力，Solovay-Strassen 测试即使使用多个底数也可能失效。这强调了在关键应用中可能需要使用更强的测试（如 Miller-Rabin 的更多轮次或确定性测试）或结合多种测试方法。
理论突破：将欧拉伪素数能通过的连续素数底数记录从之前的 12 个（Sorenson & Webster 针对强伪素数）提升到了 47 个。
算法优化：提出的基于分类和乘法构造的算法为寻找特定性质的伪素数提供了一种高效路径，避免了穷举搜索。
数学结构洞察：深入揭示了卡迈克尔数内部结构（特别是 2-进估值分布）与欧拉骗子数量之间的深刻联系，为未来研究伪素数分布提供了新的视角。

总结：这篇论文通过理论分类和算法构造，成功制造了目前已知能通过最多连续素数底数测试的欧拉伪素数（211），深刻揭示了概率素性测试在极端情况下的局限性，并为密码学安全参数的选择提供了重要的参考依据。