🔢 mathematics

U-Bit Collapse in Arnault Composites:Probing the Boundary of Strong Lucas Pseudoprimes

本文通过一项计算研究表明，专门设计用于通过所有底数至 11 的 Miller-Rabin 测试的合数，在序列退化极小的情况下，始终无法通过强 Lucas 疑似素数测试，从而为这两个素性测试组件之间的统计独立性提供了经验证据，并支持了 Baillie-PSW 型测试的鲁棒性。

原作者： Bowman Hall

发布于 2026-01-28

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Bowman Hall

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

想象一下，你是一名非常高级俱乐部的保安。想要进入俱乐部，你必须通过两种不同类型的身份验证。

米勒-拉宾检查（Miller-Rabin Check）： 这就像标准的身份证扫描。它很快，能识破大多数假证件。
卢卡斯检查（Lucas Check）： 这是一项更难、更复杂的测试。它会寻找第一项检查所遗漏的细微细节。

几十年来，数学家们一直试图制造出一个“超级假证件”（一个合数），使其设计得如此巧妙，以至于能同时骗过这两项检查。到目前为止，还没有人成功过。被称为“Baillie-PSW”的测试结合了这两项检查，至今从未被识破。

实验：制造终极假证件

在这篇论文中，作者鲍曼·霍尔（Bowman Hall）尝试使用一位名叫阿尔诺（Arnault）的数学家设计的特定蓝图来制造这些超级精巧的假证件。

你可以把阿尔诺的蓝图想象成一台生产数字的工厂机器。作者高速运行这台机器，产生了数以千计的数字。

目标： 创造出一些在第一项检查（米勒-拉宾）中表现极其出色、甚至在进行严格测试（最高到“底数 11”）时也能通过的数字。
结果： 这台机器表现得非常出色。在数千个数字中，大约每小时就能找到 20 个成功骗过第一项检查的数字。

重大发现：“U位坍缩”（U-Bit Collapse）

在获得 200 个这类“超级假证件”后，作者对它们进行了第二项更难的检查：强卢卡斯测试（Strong Lucas Test）。

他引入了一种衡量这些数字距离通过卢卡斯测试还有多远的新方法。他称之为**“U位坍缩”**。

隐喻： 想象卢卡斯测试期望看到一个巨大的、完整的巨石（大约 350 位的数据）。如果一个假证件是真的好，它应该能够将这个巨石缩小到几乎不存在（使测试失败）。
测量方式： 作者测量了这块“巨石”缩小的程度。
- 他们的期望： 出现巨大的缩减（约 350 位的坍缩），这意味着假证件通过了测试。
- 他们的发现： 巨石几乎没有缩小。
  - 平均缩减仅为 1.6 位。
  - 观察到的最大缩减为 8 位。
  - 26% 的数字完全没有缩小。 它们看起来和任何随机的、真实的数字完全一样。

这意味着什么

论文得出结论：阿尔诺的蓝图非常擅长制造看起来通过了第一项检查的数字，但在通过第二项检查方面完全无能为力。

类比： 这就像一个伪造者，他非常擅长模仿驾驶执照的字体和油墨（通过第一项检查），但他完全无法模仿全息防伪标识或微缩文字（第二项检查）。无论他如何尝试，全息标识看起来总是假的。
“正交性”（Orthogonality）： 作者使用这个词来说明这两项测试就像是两个不同的维度。擅长其中一项并不能对通过另一项提供任何帮助。它们的运作规则完全不同。

核心结论

作者进行了一场大规模实验，专门制造了一些旨在欺骗第一项测试的数字。然而，当他们试图欺骗第二项测试时，却惨败了。这些数字看起来就像普通的、真实的数字一样随机。

这让我们非常有信心，组合后的安全系统（Baillie-PSW）依然是不可破解的。用来欺骗第一部分测试的特定技巧，甚至连接近欺骗第二部分测试都做不到。要破解这个系统，你需要一种完全不同的技巧，一种我们尚未发现的技巧。

技术摘要：Arnault 合数中的 U-bit 坍缩

问题陈述
Baillie–PSW 素性检验结合了 Miller–Rabin 测试与强 Lucas 可素数测试，尽管自 1980 年以来进行了广泛搜索，但目前尚无已知的合数反例。虽然 F. Arnault 开发了通过设计特定素因子分解（卡迈克尔数）来构造能通过多个 Miller–Rabin 测试的合整数框架，但目前仍是一个开放性问题：这些构造是否可以扩展到规避 Lucas 组件。本文研究了 Arnault 型合数（特别是那些被设计为能通过高达基数 11 的 Miller–Rabin 测试的合数）是否在 Lucas 序列中表现出任何可测量的“退化”现象，从而暗示存在构建 Baillie–PSW 伪素数的路径。

研究方法
本研究利用高吞吐量构造过程生成了约 350 位的合数 $n = p_1 p_2 p_3$ 。该构造遵循 Arnault 框架，确保素因子 $p_i$ 满足条件，即 $p_i - 1$ 共享一个大的公因子 $f$ ，从而使该合数能够通过基数高达 11 的 Miller–Rabin 测试。

生成规模： 该过程在单核 ARM 实例上运行，每分钟生成约 7,700 个卡迈克尔数。
筛选标准： 从该流中筛选出通过所有基数至 11 的 Miller–Rabin 测试的合数，其产出率约为 0.015%（约每小时 20 个）。
数据集： 共收集了 200 个此类合数用于详细分析。
测试： 每个合数均使用标准判别式 $D$ （选择满足 $(D/n) = -1$ 的 $D$ ）接受强 Lucas 可素数测试。
指标： 作者引入了 U-bit 坍缩指标，定义为 $\delta = \log_2 n - \log_2(U_d \mod n)$ ，其中 $n+1 = d \cdot 2^s$ 。该指标量化了 Lucas 项 $U_d$ 相对于均匀分布在 $[0, n)$ 之间的偏差。显著的坍缩（较大的 $\delta$ ）将表明 Lucas 项异常之小，这是成为强 Lucas 伪素数的必要条件。

关键结果
对 200 个样本数据集的分析得出了以下发现：

未能规避 Lucas 测试： 所有 200 个合数均未能通过强 Lucas 测试；未发现强 Lucas 伪素数。
U-bit 坍缩微乎其微： 观察到的坍缩值相对于实现真正伪素数所需的 $\approx 350$ $\approx 350$ 位显著偏小。
- 平均 $\delta$ ： 1.61 bit。
- 中位数 $\delta$ ： 1.0 bit。
- 最大值 $\delta$ ： 8 bit（在一个 344-bit 的合数中观察到，代表减少到了 336 bit）。
- 零坍缩： 26% 的样本（52 个合数）显示没有可测量的坍缩（ $\delta = 0$ ），这意味着其 $U_d \mod n$ 值在统计学上与 $[0, n)$ 中的随机元素无异。
参数独立性： 相关性分析显示，U-bit 坍缩与 Arnault 构造参数（ $k, M$ ）或合数位大小之间不存在显著关系（ $|\rho| < 0.09$ ）。
剩余类模式： 虽然在模 35 的某些剩余类（例如 2, 8, 18, 22, 23, 32）中 prime 因子频繁出现，但没有单一模式占据主导地位，且这些模式与 Lucas 抗性并不相关。

意义与主张
论文得出结论，使合数能够规避高达基数 11 的 Miller–Rabin 测试的代数条件，并不能为规避强 Lucas 测试提供有意义的进展。作者认为，Miller–Rabin 测试和 Lucas 测试针对的是两种本质上独立的代数结构。

正交性： 研究结果为 Miller–Rabin 与 Lucas 测试的正交性提供了强有力的经验证据。规避 Lucas 测试所需的“坍缩”并非规避 Miller–Rabin 测试所用构造方法的副产品。
Baillie–PSW 的鲁棒性： 即使是在专门设计用于抵抗 Miller–Rabin 的合数样本中，观察到的 U-bit 坍缩依然极小，这进一步增强了 Baillie–PSW 测试的持续可靠性。
构造含义： 研究表明，构造 Bailllie–PSW 伪素数需要满足与标准卡迈克尔或 Arnault 构造在性质上完全不同的代数约束。论文指出，观察到的极小坍缩反映了当前构造范式的基本局限性，而非计算投入不足。

结论
这项计算研究表明，虽然 Arnault 框架对于生成 Miller–Rabin 伪素数是有效的，但无法产生具有规避 Lucas 测试所需的 Lucas 序列退化特性的合数。U-bit 坍缩指标的引入为未来的调查提供了一个定量框架，尽管数据表明，若要解决这一开放问题，可能需要超越 Arnault 范式的替代构造方法。

实验：制造终极假证件

重大发现：“U位坍缩”（U-Bit Collapse）

这意味着什么

核心结论

技术摘要：Arnault 合数中的 U-bit 坍缩

类似论文