素因数分解

素因数分解 (そいんすうぶんかい、テンプレート:Lang-en-short) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。

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

• 任意の正の整数に対して、素因数分解はただ 1 通りに決定する。（素因数分解の一意性）
• 素因数分解の結果から、正の約数やその個数、総和などを求めることができる。

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

通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。

例

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) のとき 2⁰ × 3⁰ × 5⁰ = 1

(a, b, c) = (1, 0, 0) のとき 2¹ × 3⁰ × 5⁰ = 2

(a, b, c) = (1, 1, 0) のとき 2¹ × 3¹ × 5⁰ = 6

で、これらが 360 の正の約数である。

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 を素元という。素元は既約元であるが、一般に逆は成立しない。

素元分解整域

テンプレート:Main 環 R の元を既約元の積に表すことを既約元分解、素元の積に表すことを素元分解という。既約元分解が一意であるような環を素元分解整域もしくは一意分解環という（任意の元が素元の積に表せるなら、その表し方は一意である）。有理整数全体の成す環 Z や体上の多項式環 K[x] などは素元分解整域である（高校数学でいう多項式の"因数分解"とは、通常有理数体 Q 上の一変数多項式環における素元分解のことである）。これらの環はユークリッド整域にもなっているが、一般にユークリッド整域は単項イデアル整域であり、単項イデアル整域は素元分解整域になる。

素元分解整域でない例として有理数体 Q に方程式 x² + 5 = 0 の根を添加した代数体 Q(√− 5) の整数環 Z[√− 5] で 6 を既約分解することを考えてみる。整数 Z の範囲では 2 × 3 のみであるが、Z[√− 5] の範囲では

2 × 3 = (1 + √− 5)(1 − √− 5) = 6

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

(6) = (2, 1 + √− 5)²(3, 1 + √− 5)(3, 1 − √− 5)

と分解される。

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

素因数分解の記録

Cunningham Project とは、b = 2, 3, 5, 6, 7, 10, 11, 12 および多くの自然数 n に対し、bⁿ ± 1 を素因数分解しよう、というプロジェクトである。RSA チャレンジについてはRSA暗号#RSA暗号解読コンテスト を参照。

• 2005年4月、11²⁸¹ + 1 の約数として現れる176桁の合成数が素因数分解される（一般数体ふるい法、立教大学、NTT、富士通研究所）
• 2005年5月、200桁の合成数 RSA-200（RSAチャレンジ）が素因数分解される（一般数体ふるい法、Bahr, Boehm, Franke, Kleinjung）[1]
• 2006年8月、10³⁸¹ + 1 から67桁の素数が分解される（楕円曲線法、B. Dodson）
• 2006年9月、7³⁵² + 1 の約数として現れる128桁の合成数が素因数分解される（一般数体ふるい法、情報通信研究機構、富士通、富士通研究所、フィールドプログラマブルゲートアレイおよびダイナミックリコンフィギュラブルプロセッサを用いた専用ハードウェアを初めて使用）
• 2007年5月、2¹⁰³⁹ − 1 の約数として現れる307桁の合成数が素因数分解される（特殊数体ふるい法、NTT、ドイツのボン大学、スイス連邦工科大学との共同研究）
• ？？？200桁（663ビット）
• 2010年1月、232桁(768ビット）（NTT、スイス連邦工科大学ローザンヌ校(EPFL)、独ボン大学、フランス国立情報学自動制御研究所(INRIA)、オランダ国立情報工学・数学研究所(CWI)。一般数体ふるい法。300台PCの並列計算処理。約３年）

関連項目

• 約数
• 公約数
• 算術の基本定理
• 倍数
• 約数関数
• 公開鍵暗号
• イデアル
• 代数体
• デデキント環

参考

• 和田秀男、『コンピュータ素因子分解』、遊星社、1987、改訂版 1999、ISBN-13: 978-4795268890
• 和田秀男、『素数全書－計算からのアプローチ』（訳書、R.Crandall、C.Pomerance著）、朝倉書店、2010、ISBN-13: 978-4254111286

外部リンク

• Cunningham Project