因数分解（因数分解、ファクタリングとも呼ばれる）とは、ある整数を、掛け合わせて元の数になるより小さな整数（因子、あるいは除数）の積に分解する操作です。例えば 12 = 3 × 4 や 12 = 2 × 6 といった表し方が因数分解の例です。なお、1 は任意の整数の因子（どの整数も1で割り切れる）ですが、1自体は素数でも合成数でもありません。

素因数分解の定義

素因数分解とは、合成数を素数だけの積で表すことです。言い換えれば、ある整数を「素数の掛け算」の形に分解することを指します。例えば：

  • 4 は素数ではないため、4 自身は素因数ではありません。4 の素因数分解は 2 × 2 です。
  • 12 の素因数分解は通常 2 × 2 × 3、あるいは指数表記で 2^2 × 3 と書きます。
  • 72 の素因数分解は 2^3 × 3^2 です（因子は小さい順に並べることが多いです）。

一意性（算術の基本定理）

自然数 1 より大きい任意の整数は、素数の積として表すことができ、その表し方は順序を除いて一意である、というのが算術の基本定理（基本定理 of arithmetic）です。これを簡単にまとめると：

  1. 任意の整数（1 より大きい）は素数の積として表せる（存在）。
  2. その素因数分解は順序を入れ替える以外に重複がない（一意性）。

一意性の直感的な理由は、ある素数が積の一方に現れれば必ずもう一方にも現れる必要があり、これを繰り返すことで両方の分解の素因数が一致することが示せるためです（形式的にはユークリッドの補題などを使って証明します）。

因数分解の実用的な側面

小さな数の因数分解は手計算や単純なアルゴリズム（試し割り）で容易にできますが、桁数が非常に大きい整数の場合、素因数を求めるのは計算上非常に難しくなります。この「大きな数の素因数分解が難しい」という性質を利用しているのが現代の公開鍵暗号方式の一つです。例えば：

  • RSA暗号は、二つの大きな素数の積（いわゆる半素数）を公開鍵とし、その因数分解が実用的に困難であることに安全性を依存しています。
  • 現在の実装では数百〜数千ビット長の素数が使われ、素因数分解の困難さが安全性の根拠となっていますが、量子アルゴリズム（例：ショアのアルゴリズム）が実用化されれば影響を受ける可能性があります。

因数分解の代表的手法（概略）

大きな数を因数分解するためのアルゴリズムはいくつかあり、規模によって適する方法が異なります。代表的なものを簡単に紹介します：

  • 試し割り（単純だが非効率）: 小さな素数から順に割り切れるか試す方法。小さい数には有効。
  • ポラードのρ法（Pollard's rho）: 中程度の大きさの数に有効な確率的アルゴリズム。
  • 二次篩（Quadratic Sieve）: 中〜大規模の数に効率的なアルゴリズム。
  • 一般数体篩（General Number Field Sieve, GNFS）: 現在、非常に大きな一般的な整数（公開鍵サイズの半素数など）に対して最も高速な既知の古典的アルゴリズム。

手で因数分解する簡単な手順（例）

簡単な例として 84 を素因数分解する手順：

  1. 最小の素数 2 で割れるか確認：84 ÷ 2 = 42 → 2 は因子。
  2. 42 をさらに 2 で割る：42 ÷ 2 = 21 → もう一つ 2。
  3. 21 は 2 で割れないので次の素数 3 を試す：21 ÷ 3 = 7 → 3 は因子。
  4. 残った 7 は素数なので終了。結果：84 = 2^2 × 3 × 7。

このように、因数分解と素因数分解は整数論の基本かつ応用面でも重要な概念です。特に暗号分野では「分解の難しさ」が実用的な安全性を生み出す重要な性質になっています。