素因数分解 計算ツール｜素数判定・約数列挙・GCD/LCM・整数論の基礎

素因数分解と算術の基本定理

任意の2以上の整数 n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ（p_iは素数）

素因数分解とは、正の整数を素数のべき乗の積として表すことです。例えば 360 = 2³ × 3² × 5、1024 = 2¹⁰、2026 = 2 × 1013となります。この分解は算術の基本定理(素因数分解の一意性定理)により、順序を除いて一意に決定されることが証明されています。

素数の定義

• 1とその数自身以外に正の約数を持たない、2以上の自然数
• 最小の素数は2、最初の10個は 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
• 1は素数ではありません(算術の基本定理の一意性が崩れるため)
• 2は唯一の偶数の素数(3以上の素数はすべて奇数)
• 素数は無限に存在する(ユークリッドの定理、紀元前300年頃)

合成数と素数の分布

合成数は2つ以上の素数の積で表される数です。素数定理(1896年アダマール・プーサン)により、n以下の素数の個数はおよそn / ln(n)で近似されます。100以下の素数は25個、1000以下は168個、100万以下は78,498個。素数は無限にありますが、大きくなるほど「まばら」になります。

計算アルゴリズム(試し割り法)

本ツールは試し割り法(trial division)を実装しています。2から√nまでの整数で順に割ってみるシンプルな方法で、10⁹程度までは高速に動作します。

手順

1. iを2から順にnを割っていく
2. i×i > n になるまで続ける(√n を超えたら残ったnは素数)
3. 割り切れたらnを更新し、素因数のカウントを増やす
4. 最後に残ったn>1があれば、それも素因数

効率化のポイント

大きな数(20桁以上)ではポラード・ロー法、二次篩法、一般数体篩法(GNFS)など高度な手法が必要です。世界最速の素因数分解記録はGNFSにより829ビット(250桁)の合成数を分解した2020年の記録。RSA-2048(2048ビット)を分解できる古典的アルゴリズムは実用上存在しません。

エラトステネスの篩

紀元前3世紀にエラトステネスが発明した、n以下の全素数を列挙する古典アルゴリズム。「2の倍数、3の倍数…」を順に消していき、残ったものが素数。時間計算量O(n log log n)で極めて効率的。中学の教科書に登場します。

100以下の素数早見表(全25個)

100以下の素数を暗記しておくと、中学高校の入試問題で素因数分解が瞬時に出せるようになります。

約数の個数・和の公式

素因数分解 n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ から、以下が直接計算できます。

約数の個数 τ(n) の公式

τ(n) = (a₁+1)(a₂+1)…(aₖ+1)

例: 360 = 2³ × 3² × 5 → τ(360) = 4×3×2 = 24個

約数の和 σ(n) の公式

σ(n) = (p₁^(a₁+1)-1)/(p₁-1) × … × (pₖ^(aₖ+1)-1)/(pₖ-1)

例: 360 → σ(360) = 15 × 13 × 6 = 1170

完全数・不足数・過剰数

• 完全数: σ(n) - n = n となる数(自身を除く約数の和が自身と等しい)。6, 28, 496, 8128...
• 不足数: σ(n) - n < n(自身より小さい)。ほとんどの整数がこれ
• 過剰数: σ(n) - n > n(自身より大きい)。12, 18, 20, 24...

完全数はメルセンヌ素数と1対1対応することが証明されており、2024年時点で既知の完全数は52個のみです(すべて偶数)。奇数の完全数の存否は未解決問題。

GCD/LCMへの応用

素因数分解は最大公約数(GCD)・最小公倍数(LCM)の計算に直結します。

公式

GCD(a,b) = 共通素因数の最小指数の積
LCM(a,b) = 全素因数の最大指数の積

例: GCD(360, 420) と LCM(360, 420)

• 360 = 2³ × 3² × 5
• 420 = 2² × 3 × 5 × 7
• GCD = 2² × 3 × 5 = 60(共通素因数の小さい方の指数)
• LCM = 2³ × 3² × 5 × 7 = 2520(全素因数の大きい方の指数)
• 関係式: GCD × LCM = a × b(360 × 420 = 60 × 2520 = 151,200)

ユークリッドの互除法

実務でGCDを高速計算する場合、素因数分解ではなくユークリッドの互除法を用います。「大きい数を小さい数で割った余りを取る」を繰り返すだけで、桁数の対数オーダーで計算完了。紀元前300年に発見されたアルゴリズムが現代のRSA・楕円曲線暗号でも使われています。

RSA暗号とセキュリティ

RSA暗号(1977年、Rivest・Shamir・Adleman)は、公開鍵暗号の代表格。「大きな合成数の素因数分解が困難」という数学的事実に安全性の基礎を置いています。

仕組みの概要

1. 2つの大きな素数 p, q(通常1024ビット以上)を選ぶ
2. n = p × q を計算(公開)、p, q は秘匿
3. 公開鍵で暗号化、秘密鍵(p, qから導出)で復号
4. 攻撃者は n から p, q を求めない限り復号不可能

安全性の根拠

2048ビット(617桁)のnを素因数分解するには、現存する最速アルゴリズムでも数千年〜数万年かかると推定されます。ただし量子コンピュータのショア(Shor)アルゴリズムが実用化されれば多項式時間で分解可能。米国NIST(国立標準技術研究所)は2024年に量子耐性暗号(CRYSTALS-Kyber等)の標準を確定し、移行を開始しています。

実際の応用

• HTTPS通信(TLS/SSL)の鍵交換
• 電子署名・PKI(公開鍵基盤)
• マイナンバーカードのICチップ内認証
• SSH・PGP等のセキュア通信

メルセンヌ素数・GIMPS

メルセンヌ素数は 2^p − 1 の形をした素数で、pも素数である場合に現れます。M₂ = 3, M₃ = 7, M₅ = 31, M₇ = 127...と続きます。

2024年時点の最大素数

M₁₃₆,₂₇₉,₈₄₁ = 2^136,279,841 − 1(約4,102万桁、2024年10月発見)が現時点の最大既知素数。この発見はGIMPS(Great Internet Mersenne Prime Search)という分散コンピューティングプロジェクトの成果。世界中のボランティアがCPUの空き時間を提供して探索しています。

完全数との関係

ユークリッドとオイラーの定理により、偶数の完全数はメルセンヌ素数 Mₚ を用いて 2^(p-1) × Mₚ の形で表されることが証明されています。新しいメルセンヌ素数の発見は、同時に新しい完全数の発見でもあります。

賞金と応用

EFF(電子フロンティア財団)は1億桁を超える素数の発見に15万ドルの賞金を提供。金融的な意味は薄いですが、疑似乱数生成器の周期分析、耐フォールト分散システムのテストなど数学以外にも応用があります。

場面別の使い方

よくある間違い・注意点

• 1を素数と誤解 — 1は素数ではありません。算術の基本定理(素因数分解の一意性)を成立させるため、素数の定義から意図的に除外されています。
• 0の素因数分解を考える — 0は素因数分解の対象外。素因数分解は正の整数(2以上)に対して定義されます。1は「素因数を持たない」と扱います。
• 試し割りをnまで実行してしまう — √n を超えた時点で残ったnは素数と確定します。上限を√nにしないと、10⁹の判定に膨大な時間がかかります。
• 約数の個数を数え上げで計算 — 素因数分解 n = p₁^a₁ × … × pₖ^aₖ から τ(n) = (a₁+1)(a₂+1)…(aₖ+1) で瞬時に求まります。全約数を列挙する必要はありません。
• 合成数と素数の判定を混同 — 合成数は素数以外の2以上の整数(1は素数でも合成数でもない)。中学入試では「素数・合成数・1」の3分類が問われることがあります。
• 大きな数(20桁超)を試し割り法で分解しようとする — 実用範囲は10⁹〜10¹²程度まで。20桁超はポラード・ロー法、50桁超は数体篩法など高度な手法が必要。RSAの安全性の根拠です。
• 素数の分布を線形と誤解 — 素数はn/ln(n)個(素数定理)で、nが大きくなるほどまばらになります。100までに25個、1000までに168個、100万までに78,498個。

関連する定理・数学分野

• 算術の基本定理 ― 2以上の整数は素数の積として順序を除いて一意に表せる。素因数分解の理論的支柱。
• ユークリッドの定理 ― 素数は無限に存在する(紀元前300年、背理法による古典的証明)。
• 素数定理 ― n以下の素数の個数 π(n) は n/ln(n) に近づく。1896年にアダマールとプーサンが独立に証明。
• フェルマーの小定理 ― pが素数、aがpと互いに素なとき a^(p-1) ≡ 1 (mod p)。RSA暗号の基礎。
• Riemann仮説 ― リーマンゼータ関数の非自明零点はすべて実部1/2の直線上にある、という素数分布に関する未解決問題。100万ドルの懸賞金(クレイ数学研究所ミレニアム問題)。
• ゴールドバッハ予想 ― 4以上の偶数は2つの素数の和で表せる。18世紀提起、現在も未解決。
• 双子素数予想 ― 差が2の素数(11と13、17と19等)が無限にあるという予想。未解決。
• 整数論・解析的数論・代数的数論 ― 素数と整数の性質を扱う純粋数学の主要分野。

参考文献・公的資料

より深く整数論・素数を学びたい方向けの、大学・公的機関・国際学術団体の一次資料です。

• MathWorld: Prime Number ― Wolfram Researchによる数学百科事典。素数の定義・性質・歴史・関連定理を包括的に解説。
• OEIS: A000040 (素数の列) ― オンライン整数列大辞典。素数列の完全なデータベースと関連情報。
• GIMPS (Great Internet Mersenne Prime Search) ― 世界最大の素数探索プロジェクト。既知の最大素数と歴代記録、参加方法。
• Clay Mathematics Institute: Riemann Hypothesis ― ミレニアム懸賞問題の一つ、リーマン仮説の公式解説。
• American Mathematical Society (AMS) ― 米国数学会の学術誌Notices of the AMS。整数論・素数関連の最新研究を掲載。
• NIST Post-Quantum Cryptography ― 米国国立標準技術研究所による量子耐性暗号標準化プロジェクト。RSAの将来的な置き換え。
• 日本数学会 ― 日本の数学者による学術団体。整数論分科会が素数・数論の研究を推進。
• J-STAGE 数学(日本数学会) ― 日本数学会機関誌の電子アーカイブ。整数論の日本語論文を検索・閲覧可能。
• 文部科学省 学習指導要領(中学校数学) ― 中学3年で素因数分解を扱う根拠。学習指導要領の公式解説。
• Prime Pages (テネシー大学マーティン校) ― Chris Caldwell教授による素数専門情報サイト。歴代最大素数リスト、素数判定アルゴリズム解説。

よくある質問（FAQ）

関連計算ツール