素数の分析

素数の性質を系統的に分析する。素数判定アルゴリズムの選択と適用、素因数分解の実行、素数の分布に関する定理の活用、および数論的関数（オイラーのトーシェント関数、メビウス関数）の計算を含む。

使用タイミング

• 与えられた数が素数かどうかを判定する場合
• 合成数の素因数分解を行う場合
• 一定範囲内のすべての素数を列挙する場合
• 素数定理を使用して素数の近似個数を推定する場合
• オイラーのトーシェント関数やメビウス関数を計算する場合
• RSA暗号などの暗号学的応用の基礎を理解する場合

入力

• 必須: 分析対象の数（素数判定）、または分析すべき範囲（素数の列挙）
• 必須: 分析タイプ（素数判定、素因数分解、範囲内列挙、数論的関数の計算）
• 任意: 使用するアルゴリズムの指定
• 任意: 確率的判定の許容誤差

手順

ステップ1: 問題の分類とアルゴリズムの選択

分析タイプと数の大きさに基づいて適切なアルゴリズムを選択する：

1. 小さい数（< 10^6）: 試し割り法またはエラトステネスの篩
2. 中程度の数（10^6 - 10^18）: ミラー-ラビン素数判定（確率的）
3. 大きい数（> 10^18）: ミラー-ラビンまたはAKS素数判定（決定的）
4. 素因数分解: 試し割り → ポラードのρ法 → 二次篩法 → 数体篩法（数の大きさに応じて）

期待結果： 数の大きさと分析タイプに適したアルゴリズムが選択される。

失敗時： アルゴリズムの計算量が許容範囲を超える場合は、確率的方法に切り替えて誤差の上限を明示する。

ステップ2: 素数判定の実行

選択したアルゴリズムで素数判定を実行する：

1. 試し割り法: √n以下のすべての素数で割り切れるか検査する。O(√n)。
2. エラトステネスの篩: 2からnまでの配列で合成数を消していく。O(n log log n)。
3. ミラー-ラビン判定: n-1 = 2^s × dの分解を行い、ランダムな基底aに対してフェルマーの小定理の変形を検証する。
4. 結果の記録: 素数ならば「素数」、合成数ならば因数とともに記録する。

期待結果： 素数判定が正確に完了し、結果が記録される。

失敗時： ミラー-ラビン判定で偽陽性が懸念される場合は、複数の基底（最低10個）でテストするか、決定的テスト（特定の基底の組み合わせ）を使用する。

ステップ3: 素因数分解の実行

合成数の完全な素因数分解を求める：

1. 小さい因数の除去: 2、3、5、7、...と順に割り、小さい素因数を除去する。
2. ポラードのρ法: 擬似乱数列 x_{n+1} = x_n² + c (mod n) を生成し、gcd(|x_i - x_j|, n)で因数を検出する。
3. 再帰的分解: 見つかった因数が合成数の場合は、さらに分解を続ける。
4. 一意性の確認: 算術の基本定理により、素因数分解は（順序を除いて）一意。

期待結果： 完全な素因数分解 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ が得られる。

失敗時： 大きな半素数（2つの大きな素数の積）の場合、ρ法では時間がかかる。二次篩法や数体篩法の使用を検討する。

ステップ4: 数論的関数の計算

素因数分解を利用して数論的関数を計算する：

1. オイラーのトーシェント関数: φ(n) = n × ∏(1 - 1/p)（pはnの素因数）
2. 約数関数: σ₀(n)（約数の個数）= ∏(aᵢ + 1)、σ₁(n)（約数の和）= ∏(pᵢ^(aᵢ+1) - 1)/(pᵢ - 1)
3. メビウス関数: μ(n) = (-1)^k（nがk個の異なる素因数の積の場合）、μ(n) = 0（平方因子がある場合）
4. 位数と原始根: φ(n)の約数を検査して乗法的位数を求める。原始根の存在条件を確認する。

期待結果： 要求された数論的関数の値が正確に計算される。

失敗時： 素因数分解が不完全な場合は、数論的関数の計算も不完全になる。まず完全な素因数分解を確保すること。

バリデーション

• アルゴリズムが数の大きさに適している
• 素数判定の結果が正しい（小さい数は検算可能）
• 素因数分解の積が元の数に等しい
• すべての因数が素数である
• 数論的関数の値が正しい（既知の値との照合）

よくある落とし穴

• 1は素数ではない: 素数の定義は「1より大きい自然数で、1と自分自身以外に正の約数を持たない数」。1は素数でも合成数でもない。
• ミラー-ラビンの偽陽性: 確率的テストでは合成数を素数と誤判定する可能性がある。高い確実性が必要な場合は十分な回数テストを繰り返す。
• 試し割りの上限: √nまでで十分。√nを超える因数が存在する場合、n/pは√n未満であり、既にチェック済み。
• 素因数分解の計算困難性: RSA暗号の安全性は大きな数の素因数分解が計算困難であることに依存する。この困難性は証明されていないが、広く信じられている。

関連スキル

• solve-modular-arithmetic

  -- 素数が関わる合同算術

• explore-diophantine-equations

  -- 素数の性質を利用した整数方程式