素因数分解
出典: フリー百科事典『ウィキペディア（Wikipedia）』
素因数分解（そいんすうぶんかい）とは、ある正の整数を素数の積の形で表す方法のことである。ただし、1 に対する素因数分解は 1 と定義する。
素因数分解には次のような性質がある。
- 任意の正の整数に対して、素因数分解はただ 1 通りに決定する。これを素因数分解の一意性と呼ぶ。
- 素因数分解の結果を利用して、約数や約数の総和などを導き出す事が出来る。
インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解の難易さと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。
通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。
目次 |
[編集] 例
360 を素因数分解する。
この右辺から分かることは、360 の約数は
- 2a × 3b × 5c
の形をしていて、指数は
- 0 ≤ a ≤ 3
- 0 ≤ b ≤ 2
- 0 ≤ c ≤ 1
の範囲に限られるということである。例えば
- (a, b, c) = (0, 0, 0) にあたる 360 の約数は 20 × 30 × 50 = 1
- (a, b, c) = (1, 0, 0) にあたる 360 の約数は 21 × 30 × 50 = 2
- (a, b, c) = (1, 1, 0) にあたる 360 の約数は 21 × 31 × 50 = 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, Elliptic curve method)
- 複数多項式2次ふるい法 (MPQS, Multiple polynomial quadratic sieve)
- 数体ふるい法 (NFS, Number field sieve)
- 一般数体ふるい法 (GNFS, General number field sieve)
- 特殊数体ふるい法 (SNFS, Special number field sieve)
[編集] 素元分解
整域において素因数分解（のようなもの）を考える問題は、代数学における古典的な問題のひとつである。
一般に環構造を持った集合 R においては、「割り切る」という関係を単項イデアルの包含関係により定めることができる。すなわち、a, b ∈ R の生成する単項イデアル (a) = aR, (b) = bR に対し、(a) ⊃ (b) のときに a|b と書いて、a は b を割り切るとか、a は b の約元であるとか、b は a の倍元であるなどとかいう。言い換えると、a が b を割り切るとは、a = bc を満たすような R の可逆でも 0 でもない元 c が存在することをいう。
可逆でも 0 でもない R の元が、2つの非可逆元の積として表せるとき、可約であるといい、そうでないとき既約であるという。単項イデアル (p) が自明でない素イデアルであるとき、p を素元という。素元は既約元であるが、一般に逆は成立しない。
[編集] 素元分解整域
詳細は「素元分解整域」を参照
環 R の元を既約元の積に表すことを既約元分解、素元の積に表すことを素元分解という。既約元分解が一意であるような環を素元分解整域もしくは一意分解環という（任意の元が素元の積に表せるなら、その表し方は一意である）。有理整数全体の成す環 Z や体上の多項式環 K[x] などは素元分解整域である（高校数学でいう多項式の"因数分解"とは、通常有理数体 Q 上の一変数多項式環における素元分解のことである）。これらの環はユークリッド整域にもなっているが、一般にユークリッド整域は単項イデアル整域であり、単項イデアル整域は素元分解整域になる。
素元分解整域でない例として有理数体 Q に方程式 x2 + 5 = 0 の根を添加した代数体 Q(√−5) の整数環 Z[√−5]で6を既約分解することを考えてみる。整数 Z の範囲では 2 × 3 のみしかありえないが、Z[√-5] の範囲では
という二通りの既約分解が可能になる。したがってZ[√−5] は素元分解整域ではない。しかし、イデアルとしては (2), (3) や (1 ± √-5) はさらに分解できて、素イデアルの積としては一意的に
と分解される。
このような考察はクンマーの理想数の理論に始まると考えられる。クンマー以降、デデキントのイデアル論などを経て代数的整数論の基盤となっている。
[編集] 素因数分解の記録
Cunningham Project とは、b = 2, 3, 5, 6, 7, 10, 11, 12 および多くの自然数 n に対し、bn ± 1 を素因数分解しよう、というプロジェクトである。RSA チャンレンジについてはRSA暗号#RSA Challenge 解読コンテスト結果を参照。
- 2005年4月、11281 + 1 の約数として現れる176桁の合成数が素因数分解される（一般数体ふるい法、立教大学、NTT、富士通研究所）
- 2005年5月、200桁の合成数 RSA-200（RSAチャレンジ）が素因数分解される（一般数体ふるい法、Bahr, Boehm, Franke, Kleinjung）[1]
- 2006年8月、10381+1から67桁の素数が分解される（楕円曲線法、B. Dodson）
- 2006年9月、7352 + 1 の約数として現れる128桁の合成数が素因数分解される（一般数体ふるい法、情報通信研究機構、富士通、富士通研究所、フィールドプログラマブルゲートアレイおよびダイナミックリコンフィギュラブルプロセッサを用いた専用ハードウェアを初めて使用）
- 2007年5月、21039 - 1 の約数として現れる307桁の合成数が素因数分解される（特殊数体ふるい法、NTT、ドイツのボン大学、スイス連邦工科大学との共同研究）
