素因数分解

出典: フリー百科事典『ウィキペディア（Wikipedia）』

素因数分解（そいんすうぶんかい）とは、ある正の整数を素数の積の形で表す方法のことである。ただし、1 に対する素因数分解は 1 と定義する。

素因数分解には次のような性質がある。

任意の正の整数に対して、素因数分解はただ 1 通りに決定する（ただし、順序は問わない）。
素因数分解の結果を利用して、約数や約数の総和などを導き出す事が出来る。

インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は巨大な合成数の素因数分解の難易さと深い関わりがあり、またRSA以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。

[編集] 例

360 を素因数分解する。

360 = 2³ × 3² × 5¹

この右辺から分かることは、360 の約数は

2^a × 3^b × 5^c

の形をしていて、指数は

0 ≤ a ≤ 3

0 ≤ b ≤ 2

0 ≤ c ≤ 1

の範囲に限られるということである。例えば

(a, b, c) = (0, 0, 0) にあたる 360 の約数は 2⁰ × 3⁰ × 5⁰ = 1

(a, b, c) = (1, 0, 0) にあたる 360 の約数は 2¹ × 3⁰ × 5⁰ = 2

(a, b, c) = (1, 1, 0) にあたる 360 の約数は 2¹ × 3¹ × 5⁰ = 6

などのように表せる。

a は 0 から 3 までの4通りの数を取り、b は 0 から 2 までの3通りの数を取り、c は 0 から 1 までの2通りの数を取ることを考えれば (a, b, c) は 4 × 3 × 2 = 24 通りの組み合わせがあることになる。このことより、360 の約数は 24 個あると分かる。実際に 360 の約数は

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360

の 24 個である。

[編集] 素因数分解アルゴリズム

正の整数 n を素因数分解するための最も単純な方法は、2 から順に √n までの素数で割っていく方法である。しかし、n が大きくなると、この方法では困難である。

大きな n に対しては以下のような方法がある。

ρ法（ポラード・ロー素因数分解法）
p-1法
p+1法
連分数法
楕円曲線法(ECM)
複数多項式2次ふるい法(MPQS)
数体ふるい法(NFS)

[編集] 素元分解

一般に環構造を持った集合 R においては "割り切る" という関係を単項イデアルの包含関係により定めることができる。すなわち、a, b ∈ R の生成する単項イデアル (a) = aR, (b) = bR について

a|b ⇔ (a) ⊃ (b)

と書いて、a は b を割り切るとか、a は b の約元であるとか、b は a の倍元であるなどとかいうわけである。これはつまり、a = bc を満たすような R の可逆でも 0 でもない元 c が存在することを a が b を割り切ると言っているのである。

R の元 p が、 R の可逆元しか約元として持たないなら既約であるといい、そうでないなら可約であるという。p が既約元であることと単項イデアル (p) が素イデアルになることとは同値である。この意味で p は素元であるということもある。

[編集] 一意分解環

環 R の元を既約元の積に表すことを既約元分解、素元分解という。この表し方が一意であるような環を一意分解環あるいは素元分解環という。有理整数全体の成す環 Z や体上の多項式環 K[x] などは一意分解環である^[1]。これらの環は単項イデアル整域にもなっているが、一般に単項イデアル整域は一意分解環になる。

[編集] 代数体の数論とイデアル

既約元分解としての素因数分解を代数的整数の範囲で行うとき、一意性を持たなくなることがありうる。また、整数の範囲で素数（既約元）であったものがそうでなくなることが起こりうる。

例として有理数体 Q に方程式 x² + 5 = 0 の根を添加した代数体 Q(√−5) の整数環 Z[√−5] の範囲で 6 を既約分解する。

整数　Z の範囲では 2 × 3 のみしかありえないが、Z[√-5] の範囲では

$2 \times 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}) = 6$

という二通りの既約分解が可能になる。しかしながら、イデアルとしては (2), (3) や (1 ± √-5) はさらに分解できて、素イデアルの積としては一意的に

$(6) = (2, 1 + \sqrt{-5})^2 (3, 1 + \sqrt{-5})(3, 1 - \sqrt{-5})$

と分解される。

このような考察はクンマーの理想数の理論に始まると考えられる。クンマー以降、デデキントのイデアル論などを経て代数的整数論の基盤となっている。

[編集] 素因数分解の記録

RSAチャンレンジについてはRSA暗号#RSA Challenge 解読コンテスト結果を参照。

2005年4月 176桁の合成数（11,281+ の C176、Cunningham Project）が素因数分解される（GNFS、立教大学、NTT、富士通研究所、世界記録）
2005年5月 200桁の合成数 RSA-200（RSAチャレンジ）が素因数分解される（GNFS、Bahr, Boehm, Franke, Kleinjung、世界記録）
2006年8月 67桁の素数（10,381+ の P67、Cunningham Project）が分解される（ECM、B. Dodson、ECMによる世界記録）
2006年9月 128桁の合成数（7,352+ の C128、Cunningham Project）が素因数分解される（GNFS、情報通信研究機構、富士通、富士通研究所、フィールドプログラマブルゲートアレイおよびダイナミックリコンフィギュラブルプロセッサを用いた専用ハードウェアを初めて使用）