Back

ⓘ 素因数分解 とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。 素因数分解には次のような性質がある。 素因数分解の結果 ..




                                     

ⓘ 素因数分解

素因数分解 とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。

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

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

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

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

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

                                     

1. 素因数分解アルゴリズム

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

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

  • 特殊数体ふるい法 SNFS, Special number field sieve
  • p + 1 法
  • 一般数体ふるい法 GNFS, General number field sieve
  • 複数多項式2次ふるい法 MPQS, Multiple polynomial quadratic sieve
  • p − 1 法
  • ρ 法(ポラード・ロー素因数分解法)
  • 楕円曲線法 ECM, Elliptic curve method
  • 連分数法
  • 数体ふるい法 NFS, Number field sieve
                                     

2. 素元分解

整域において素因数分解(に相当する概念)を考える問題は、代数学における古典的な問題の一つである。

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

                                     

2.1. 素元分解 素元分解整域

環 R の元を既約元の積に表すことを 既約元分解 、素元の積に表すことを 素元分解 という。既約元分解が一意であるような環を素元分解整域もしくは一意分解環という(任意の元が素元の積に表せるなら、その表し方は一意である)。有理整数全体の成す環 Z や体上の多項式環 K は素元分解整域ではない。しかし、イデアルとしては 2, 3 や 1 ± √ −5 はさらに分解できて、素イデアルの積としては一意に

6 = 2, 1 + √ −5 2 3, 1 + √ −53, 1 − √ −5

と分解される。一般に、代数体の整数環はデデキント環であり、素イデアルの積に一意的に分解する。

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

                                     

3. 素因数分解の記録

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

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

4. 関連項目

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

5. 参考

  • 山本, 芳彦『数論入門』岩波書店〈現代数学への入門〉、2003年。ISBN 4-00-006878-4。
  • 和田秀男、『素数全書-計算からのアプローチ』(訳書、R.Crandall、C.Pomerance著)、朝倉書店、2010、ISBN 978-4254111286
  • 和田秀男、『コンピュータ素因子分解』、遊星社、1987、改訂版 1999、ISBN 978-4795268890
                                     
  • の3つである また 7 は素数であるため 7 の 素因数 は 7 自身のみとなる 素因数 のことを 素因 子 そいんし 素因数分解 のことを 素因 子 分解 ということもある 2つの自然数が互いに 素 であることと 2つの自然数が共通の 素因数 を持たないことは同値である なお 1 は 素因数 を持たない数であり したがって 1 は全ての 1
  • 数学における 因数分解 いんすうぶんかい 英: factorization, factoring, decomposition 分解 因子 分解 は 与えられた数学的対象を同種の しかし普通はより小さいあるいはより平易な 別の対象 - それは 因数 factor 因子 乗法因子 乗因子 と呼ばれる - の積として書き表すことを言う たとえば 15
  • ポラード ロー 素因数分解 法 英: Pollard s rho algorithm は 特殊用途の 素因数分解 アルゴリズム 1975年 ジョン ポラード 英語: John Pollard が発明した 合成数を 素因数 に効率的に 分解 する 一般に 素因数分解 は 対象の数 n について その平方根以下の全ての素数について
  • と2つの異なる方法で 分解 できてしまう ここで現れる4つの 因数 9, 21, 33および77は すべてここでいう擬素数である 素因数分解 の一意性は このタイプの数の体系に関しては成立しないのである 抽象代数学において この定理をもっと一般の場合に 仮説 として持ち込むならば 定理の主張は 任意の 0 でない元は 素
  • レピュニットは 2と5を除く素数の積で構成されている 基数 10 のレピュニットの R1 から R120 までの 素因数分解 の一覧を示す 背景が水色のセルは n が素数の場合の Rn を示す 素因数 の数 含重複 10以外の基数に対してもレピュニットを定義することができる 基数 a に対してレピュニットは
  • 因数分解 が その原始成分の整数環上での 因数分解 と同じことであることをも意味する 他方 整係数多項式の整数環上での 因数分解 は その原始成分の 分解 と内容の 素因数分解 とを掛けることで与えられる 言い方を変えれば 整数のGCD計算によって有理係数多項式の 因数分解 は整係数原始多項式の 因数分解
  • RSA暗号 RSAあんごう とは 桁数が大きい合成数の 素因数分解 問題が困難であることを安全性の根拠とした公開鍵暗号の一つである 暗号とデジタル署名を実現できる方式として最初に公開されたものである RSA暗号方式は 1977年に発明され 発明者であるロナルド リベスト アディ シャミア レオナル
  • 分解 ぶんかい とは 1種類の物を2種類以上に分ける 分かれる事 化学 分解 - 化学 物質 物理変化と化学変化の例 - 物理 因数分解 素因数分解 多項式の 因数分解 素 元 分解 射の 分解 英語版 多様体の 分解 英語版 JSJ 分解 英語版 あるいはトーラス 分解 3次元多様体の 分解 行列の 分解
  • 素因数分解 問題を解くことが等価であることが証明された初の暗号である Rabin暗号は1979年 マイケル ラビンにより発明された この暗号はRSA暗号と同じく 大きな合成数の 素因数分解 の困難さを安全性の根拠とした暗号方式である この暗号は 鍵となる合成数が 素因数分解