🔢 mathematics

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

この論文では、カルマイケル数の部分集合を分類し、既知のエーラー擬素数を乗算して高速に新たなものを生成するアルゴリズムを開発することで、最初の 47 個の素数底（2 から 211 まで）すべてに対してエーラー擬素数として機能する新しい数を見出したことを報告しています。

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

公開日 2026-02-26

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

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

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

「211 まで生き残った偽物の素数」：数学のトリックと大冒険

この論文は、**「素数（しゅうすう）」という数学の重要な要素を、「偽物（ニセモノ）」**で欺こうとする挑戦の物語です。

現代のインターネットのセキュリティ（銀行取引や暗号通信など）は、巨大な「素数」の存在に支えられています。しかし、コンピュータが「これは素数だ！」と判断するテストには、実は**「素数そっくりの偽物（擬素数）」**が潜んでいる可能性があります。

この論文の著者たちは、**「いかに多くのテストをすり抜ける、最強の偽物」**を見つけ出し、その限界を「211」という数字まで押し広げました。

以下に、専門用語を排し、日常の比喩を使ってこの研究を解説します。

1. 舞台設定：素数チェックという「セキュリティゲート」

まず、素数を見つけるための「テスト（検査）」があると想像してください。

素数：本物のダイヤモンド。どんな検査も完璧にパスします。
合成数：ガラスやプラスチックの偽物。通常は検査で「偽物！」とバレます。
擬素数（Pseudoprime）：「高品質なガラス」。普通の検査では「ダイヤモンドだ！」と誤認されてしまいます。

研究者たちは、**「ソロヴァイ・ストラッセンテスト」という特定の検査に、「最初の 47 個の素数（2, 3, 5, 7...）」**すべてを「検査官」として送り込みます。

通常、偽物は最初の数人の検査官ですぐにバレます。
彼らの目標は、**「最初の 47 人の検査官全員を欺き、最後の人（211 番目の素数）まで生き残る」**ような、超高性能な偽物を作ることです。

2. 主人公の素材：「カールマイケル数」という特殊なガラス

彼らが使った素材は、**「カールマイケル数」**という特殊な合成数です。

普通の偽物：特定の検査官（特定の数字）にはバレますが、他の検査官にはバレません。
カールマイケル数：**「どんな検査官（どんな数字）に対しても、一時的に素数に見える」**という、非常に厄介な偽物です。

しかし、カールマイケル数にも弱点があります。ある特定の検査（「オイラーの基準」と呼ばれるより厳しいテスト）では、必ずバレてしまいます。
著者たちは、このカールマイケル数の**「ある特定のグループ（クラス A）」に注目しました。このグループは、他のグループに比べて「検査官を欺ける確率が圧倒的に高い（約 50%）」**という特徴を持っています。

3. 魔法のレシピ：「掛け合わせ」で巨大な偽物を作る

ここが論文の核心部分です。彼らは、**「すでにテストを生き残った偽物同士を掛け合わせる」**というアイデアを発見しました。

アナロジー：
- 偽物 A は、検査官 1〜10 にはバレませんでした。
- 偽物 B も、検査官 1〜10 にはバレませんでした。
- この 2 つを掛け合わせて「巨大な偽物 C」を作ると、**「C は 1〜10 だけでなく、11 番目の検査官にもバレない！」**という現象が起きることが証明されました。

彼らはこの「掛け合わせ」を繰り返すアルゴリズム（計算手順）を開発しました。

小さな偽物（素数 37 まで生き残るもの）を集める。
同じレベルの偽物同士を掛け合わせる。
できた大きな偽物が、さらに次の検査官（素数 41, 43...）にも耐えられるか確認する。
耐えられたら、さらに大きな偽物を作るために使う。

このようにして、**「小さな偽物を積み重ねて、巨大な城壁（巨大な合成数）」**を築き上げました。

4. 記録更新：211 までの大勝利

この「掛け合わせ」の魔法を駆使して、彼らはついに**「最初の 47 人の検査官（素数 2 から 211 まで）」**をすべて欺く偽数を見つけ出しました。

発見した偽物：
- 桁数が1230 桁もある、途方もなく大きな数字です。
- これは、**「211 番目の素数」**まで、すべての検査を「素数だ！」と誤認させることに成功しました。
- 以前の世界記録（12 番目まで）を大きく更新しました。

5. なぜこれが重要なのか？（そしてなぜ怖くないのか）

なぜ重要か？
- これは、現在の「素数判定テスト」が、意図的に作られた巧妙な偽物に対してどれほど脆弱になりうるかを示しています。
- もしハッカーが「このテストを突破する偽数」を大量に生成できれば、暗号システムが破られる可能性があります。
- この研究は、**「今のテストは十分か？もっと強いテストが必要ではないか？」**という警鐘を鳴らすものです。
なぜ怖くないか？
- この「211 まで生き残る偽物」は、**「意図的に作られたもの」**です。
- 通常のランダムな数字が、たまたまこれほど多くのテストをパスする確率は、「砂漠で砂粒を一つ拾って、それがダイヤモンドだった」レベルで低いです。
- したがって、普通のユーザーが使う暗号がすぐに破られる心配はありません。

6. 番外編：ソフィ・ジェルマン・ニセモノ

論文の最後には、カールマイケル数とは異なる、もう一つの「特殊な偽物（ソフィ・ジェルマン擬素数）」の存在も提案されています。
これは、**「2 つの素数を掛け合わせた特殊な形」**をした偽物で、カールマイケル数ほど強力ではありませんが、別の種類の「高品質なガラス」として発見されました。

まとめ

この論文は、**「数学的なトリック（カールマイケル数の分類と掛け合わせ）」を使って、「素数判定テストを突破する最強の偽物」を設計し、その限界を「211」**まで押し広げた記録です。

まるで、**「何百人もの警備員（検査官）が並ぶセキュリティゲート」を、「完璧な変装（擬素数）」**で次々とすり抜けていく、数学的なスパイ映画のような冒険でした。彼らの発見は、将来のセキュリティをより強固にするための重要な指針となっています。

論文「OURS GOES TO 211: EULER PSEUDOPRIMES TO 47 PRIME BASES」の技術的サマリー

この論文は、公開鍵暗号（RSA や Diffie-Hellman など）の安全性に不可欠な「素数生成」プロセスにおいて、確率的な素性判定テスト（特に Solovay-Strassen テスト）を回避する合成数（擬素数）の構築と分類に焦点を当てた研究です。著者らは、カールマイケル数（Carmichael numbers）の構造を深く分析し、特定のクラスに属する数を掛け合わせることで、非常に多くの素数底（base）に対して擬素数として振る舞う巨大な合成数を発見しました。

1. 問題の背景と目的

背景: RSA などの暗号システムは大きな素数に依存しています。素数の生成にはランダムな数をサンプリングし、確率的な合成数判定テスト（Solovay-Strassen や Miller-Rabin）を適用するのが一般的です。
課題: もし攻撃者が、これらのテストを「素数」として通過してしまう合成数（擬素数）を意図的に生成・提供できれば、システムは誤って合成数を素数として受け入れてしまい、セキュリティが損なわれます。
目的: Solovay-Strassen テストにおいて、連続する多くの素数底（ $2, 3, 5, \dots$ ）に対して擬素数として通過する合成数を構築し、その限界を調査すること。特に、最初の 47 個の素数底すべて（2 から 211 まで）に対して擬素数となる数を見つけることを目標としました。

2. 主要な手法と理論的基盤

2.1 カールマイケル数の分類

Solovay-Strassen テストをパスする合成数（オイラー擬素数）の候補として、すべての底に対してフェルマー擬素数となる「カールマイケル数」が最適であることに着目しました。著者らはカールマイケル数を、その指数（index） $i(n) = (n-1)/\lambda(n)$ の性質に基づいて以下のように分類しました。

クラス A: 指数 $i(n)$ $i (n)$ が偶数である場合。
- このクラスのカールマイケル数は、 $\phi(n)/2$ 個のオイラー偽数（Euler liars）を持ち、すべての底に対してヤコビ記号が 1 となります。これは合成数が持つことができるオイラー偽数の最大数です。
クラス B: 指数 $i(n)$ $i (n)$ が奇数である場合。
- さらに $B_1$ と $B_2$ に細分化されます。これらはクラス A に比べて偽数の割合が低く、特定の条件（ヤコビ記号の符号など）で制限されます。

重要な発見: 2 つのカールマイケル数 $n_1, n_2$ を掛け合わせた積 $n = n_1 n_2$ が再びカールマイケル数（かつクラス A）になるための必要十分条件を導出しました。特に、 $n_1, n_2$ がともにクラス A に属し、特定の 2 進評価（2-adic valuation）の条件を満たす場合、その積もクラス A になり、より多くの底でテストをパスする可能性が高まることが証明されました。

2.2 構築アルゴリズム（乗算による拡張）

既存のオイラー擬素数を掛け合わせることで、より多くの底でテストをパスする大きな擬素数を構築するアルゴリズムを開発しました。

原子（Atomic）の抽出: 150 より小さい素因数を持たない原子カールマイケル数（他のカールマイケル数の積ではないもの）をフィルタリングします。
同クラス・同底での乗算: 同じ素数底 $a$ までテストをパスする集合 $epsp(a)$ に属する数同士を掛け合わせます。異なる底の数を掛け合わせると、より低い方の底でテストに失敗する傾向があるため、同じ底で停止する数同士を掛け合わせる戦略を採用しました。
クラス A の維持: 入力となる数と出力となる積がともにクラス A に属するように条件を制御し、ヤコビ記号が 1 になる確率を最大化します。
再帰的構築:
- $epsp(a) $（原子）$ \to$ $epsp_2(a)$ （2 個の積）
- $epsp_2(a) \times ep sp_2(a) \to ep sp_4(a)$
- このプロセスを再帰的に繰り返し、 $epsp_{16}, ep sp_{32}$ などを構築します。

3. 主要な成果と結果

3.1 記録的なオイラー擬素数の発見

著者らは上記のアルゴリズムを用いて、以下の記録的な数値を達成しました。

発見した数: 1230 ビットの合成数。
通過した底: 最初の 47 個の素数（2, 3, 5, ..., 211）すべてに対して、Solovay-Strassen テストをパスします。
意味: この数は、211 以下のすべての整数底に対してオイラー擬素数として振る舞います。これは、Solovay-Strassen テストの失敗確率（1/2）を考慮しても、非常に稀で強力な擬素数です。

3.2 統計的洞察

クラス A の優位性: 発見された擬素数の绝大多数（99% 以上）がクラス A に属していました。これは理論的な予測（クラス A が最も多くの偽数を持つ）と一致しています。
剰余類の偏り: 発見された擬素数の多くは、120 を法として 1 に合同（ $n \equiv 1 \pmod{120}$ ）であることが統計的に確認されました。これは、小さな素数に対するヤコビ記号が 1 になる条件と整合しています。
ソフィー・ジェルマン擬素数: カールマイケル数以外に、 $n = p_1(2p_1-1)$ の形をした「ソフィー・ジェルマン擬素数」も発見され、これらも $\phi(n)/4$ 個のオイラー偽数を持つことが示されました。

4. 論文の意義と貢献

アルゴリズムの革新: カールマイケル数の構造（特にクラス分類と 2 進評価）に基づき、擬素数を効率的に構築・増幅するアルゴリズムを提案しました。これにより、単なるランダム検索ではなく、構造的に「強い」擬素数を生成可能になりました。
セキュリティへの示唆: 現在の素性判定テスト（Solovay-Strassen）が、意図的に構築された合成数に対して非常に脆弱であることを実証しました。特に、攻撃者が「悪意のある素数」を生成する能力を持つ場合、確率的テストだけでは不十分である可能性を示唆しています。
理論的限界の提示: 「47 個の連続する素数底」という具体的な数値目標を達成し、オイラー擬素数の存在可能性の限界を押し広げました。
分類理論の確立: カールマイケル数をクラス A/B に分類し、その積がどのようなクラスに属するかを決定する定理（Lemma 12 など）を提供しました。これは今後の擬素数研究の基礎となります。

結論

この論文は、カールマイケル数の深い数論的性質を利用することで、Solovay-Strassen テストに対して極めて強力な擬素数（211 までのすべての素数底を通過する数）を構築することに成功しました。これは、暗号システムの素数生成プロセスにおけるリスクを再評価する重要な成果であり、より堅牢な素性判定テストの必要性を浮き彫りにしています。