素因数分解

素因数分解︵そいんすうぶんかい、英: prime factorization︶とは、正の整数を素数の積の形で表すことである。

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

●任意の正の整数に対して、素因数分解はただ1通りに決定する。

●素因数分解の結果から、正の約数やその個数、総和などを求めることができる。

例えば48を素因数分解すると 2⁴× 3 となる。

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

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

素因数分解アルゴリズム

正の整数 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を割り切るとは、b = acを満たす、R の可逆でも 0 でもない元 cが存在することをいう。 

可逆でも 0 でもない Rの元が、2つの非可逆元の積として表せるとき、可約であるといい、そうでないとき既約であるという。単項イデアル (p) が自明でない素イデアルであるとき、p を素元という。素元は既約元であるが、一般に逆は成立しない。

一意分解環

詳細は「一意分解環」を参照

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

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

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

と本質的に異なる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、ドイツのボン大学、スイス連邦工科大学との共同研究︶

●20??年: 200桁︵663ビット︶

●2010年1月‥232桁︵768ビット︶︵NTT、スイス連邦工科大学ローザンヌ校 (EPFL)、独ボン大学、フランス国立情報学自動制御研究所 (INRIA)、オランダ国立情報工学・数学研究所 (CWI)。一般数体ふるい法。300台PCの並列計算処理。約3年︶

多項式時間で解いた記録

多項式時間で解かれた記録は以下である︵全て量子コンピュータによる記録である。︶。

• 2001年 - 15(=3×5)の分解に成功(IBM)
• 2012年 - 21(=3×7)の分解に成功(ブリストル大学)

関連項目

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

参考文献

●和田秀男﹃コンピュータと素因子分解﹄遊星社、1999年4月1日。ISBN 978-4795268890。 

●Crandall, Richard、Pomerance, Carl 著、和田秀男 訳﹃素数全書　計算からのアプローチ﹄朝倉書店、2010年9月10日。ISBN 978-4254111286。 

●山本, 芳彦﹃数論入門﹄岩波書店︿現代数学への入門﹀、2003年。ISBN 4-00-006878-4。 

●岡本和夫、森杉薫、根本博、永田潤一郎﹃未来へ広がる数学﹄ 3巻、新興出版社啓林館、2022年2月10日、25頁。ISBN 978-4-402-02187-0。 

外部リンク

●Cunningham Project