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

技術要約：Arnault組成数におけるUビット崩壊（U-Bit Collapse）

問題提起
ミラー・ラビン素数判定法と強いルカス強素数判定法を組み合わせたベイリー–PSW素数判定法は、1980年以降の広範な探索にもかかわらず、既知の合成数反例が存在しない。F. Arnaultは、特定の素因数分解を設計することで（カーマイケル数として）、複数のミラー・ラビン判定を通過する合成整数を構築するためのフレームワークを開発したが、これらの構築手法がルカス成分を回避するように拡張できるかどうかは、依然として未解決の問題である。本論文では、Arnault型の組成数、特に底（base）11までのミラー・ラビン判定を通過するように設計された組成数が、ルカス数列において、ベイリー–PSW擬素数への経路を示唆するような、測定可能な「退化（degeneracy）」を示すかどうかを調査する。

手法
本研究では、約350ビットの合成整数 $n = p_1 p_2 p_3$ を生成するために、高スループットの構築プロセスを利用した。構築はArnaultのフレームワークに従い、各素因数 $p_i$ が大きな共通因子 $f$ を共有する条件（$p_i - 1$ が $f$ を持つ）を満たすようにし、これにより当該組成数が底11までのミラー・ラビン判定を通過することを保証した。

• 生成規模: プロセスは単一コアのARMインスタンス上で実行され、毎分約7,700個のカーマイケル数を生成した。
• 選択基準: このストリームから、底11までのすべてのミラー・ラビン判定を通過する組成数を、約0.015%の収率（時給約20個）で分離した。
• データセット: 詳細な分析のために、計200個の当該組成数を収集した。
• テスト: 各組成数は、標準的な判別式 $D$（$(D/n) = -1$ となるもの）を用いて、強いルカス強素数判定にかけられた。
• 指標: 著者らは、$\delta = \log_2 n - \log_2(U_d \mod n)$ （ここで $n+1 = d \cdot 2^s$）と定義されるUビット崩壊指標を導入した。この指標は、ルカス項 $U_d$ が $[0, n)$ の範囲において一様分布からどの程度逸脱しているかを定量化する。顕著な崩壊（大きな $\delta$）は、ルカス項が異常に小さいことを示しており、これは強いルカス擬素数となるための必要条件である。

主要な結果
200個のサンプルを用いたデータセットの分析により、以下の知見が得られた。

• ルカス判定の回避失敗: 200個の組成数はすべて強いルカス判定に失敗した。すなわち、強いルカス擬素数は発見されなかった。
• 微小なUビット崩壊: 観測された崩壊値は、真の擬素数に必要とされる約350ビットの減少と比較して極めて小さかった。
  • 平均 $\delta$: 1.61 ビット。
  • 中央値 $\delta$: 1.0 ビット。
  • 最大値 $\delta$: 8 ビット（344ビットの組成数で観測され、これは336ビットへの減少を意味する）。
  • ゼロ崩壊: サンプルの26%（52個の組成数）において、測定可能な崩壊が見られなかった（$\delta = 0$）。これは、$U_d \mod n$ の値が $[0, n)$ 内のランダムな要素と統計的に区別がつかないことを意味する。
• パラメータの独立性: 相関分析の結果、Uビット崩壊とArnault構築パラメータ（$k, M$）、および組成数のビットサイズとの間に、無視できる程度の関係しか認められなかった（$|\rho| < 0.09$）。
• 剰余パターン: 35を法とする特定の剰余類（例：2, 8, 18, 22, 23, 32）が素因数の間で頻繁に現れたが、単一のパターンがデータセットを支配することなく、これらのパターンはルカス耐性と相関していなかった。

意義および主張
本論文は、底11までのミラー・ラビン判定を回避するための代数的な条件が、強いルカス判定を回避するための進展には何ら意味のある寄与をしないと結論付けている。著者らは、ミラー・ラビン判定とルカス判定の二つの構成要素は、根本的に独立した代数的構造を対象としていると論じている。

• 直交性: これらの結果は、ミラー・ラビン判定とルカス判定の直交性に関する強力な経験的証拠を提供するものである。ミラー・ラビン判定を破るために用いられる構築手法による副産物として、ルカス判定を破るための「崩壊」が生じることはない。
• ベイリー–PSWの堅牢性: ミラー・ラビン判定に抵抗するように特別に設計された組成数の高ボリュームなサンプルにおいても、顕著なUビット崩壊が見られなかったことは、ベイリー–PSW判定の継続的な信頼性を裏付けるものである。
• 構築への示唆: 本研究は、ベイリー–PSW擬素数を構築するには、標準的なカーマイケル数やArnaultの構築に見られるものとは、質的に異なる代数的制約を満たす必要があることを示唆している。観測された最小限の崩壊は、現在の構築パラダイムの根本的な限界を反映しており、計算努力の不足を反映しているのではないと本論文は断じている。

結論
本計算研究は、Arnaultのフレームワークがミラー・ラビン擬素数の生成には有効である一方で、ベイリー–PSW判定に挑戦するために必要なルカス数列の退化を生じさせる組成数を生成することには失敗することを立証した。Uビット崩壊指標の導入は、将来の調査のための定量的な枠組みを提供するものであるが、データは、ベイリー–PSWの反例を見つけるためには、Arnaultのパラダイムを超えた代替の構築手法が必要である可能性を示唆している。