|
|
| 1行目: |
1行目: |
| − | '''素因数分解''' (そいんすうぶんかい、{{lang-en-short|''prime factorization''}}) とは、ある正の[[整数]]を[[素数]]の[[積]]の形で表すことである。ただし、[[1]] に対する素因数分解は 1 と定義する<ref>[[空積]]を 1 とする規約のもと、1 を特別扱いする必要はない（すなわち 1 は 0 個の素数の積である）。また、素数 ''p'' の素因数分解は ''p'' であり（すなわち ''p'' は 1 個の ''p'' の積である）、"素数は素因数分解できない"という表現は''誤り''である。</ref>。 | + | '''素因数分解''' (そいんすうぶんかい、{{lang-en-short|''prime factorization''}}) |
| − | | |
| − | 素因数分解には次のような性質がある。
| |
| − | *任意の正の整数に対して、素因数分解はただ 1 通りに決定する。（[[素因数分解の一意性]]）
| |
| − | *素因数分解の結果から、正の[[約数]]やその個数、総和などを求めることができる。
| |
| − | インターネットでの認証等で利用されている[[公開鍵暗号]]の代表である[[RSA暗号]]の安全性は、巨大な[[合成数]]の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解の[[アルゴリズム]]が活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。
| |
| − | | |
| − | 通常の素因数分解は、有理整数環 '''Z''' で考えるが、一般の[[代数体]]の[[整数環]]においては、素因数分解の一意性に対応する性質が成り立つとは限らない。
| |
| − | | |
| − | == 例 ==
| |
| − | 360 を素因数分解する。
| |
| − | :360 = 2<sup>3</sup> × 3<sup>2</sup> × 5<sup>1</sup>
| |
| − | この右辺から分かることは、360 の正の[[約数]]は
| |
| − | :2<sup>''a''</sup> × 3<sup>''b''</sup> × 5<sup>''c''</sup>
| |
| − | の形をしていて、[[冪乗|指数]]は
| |
| − | :0 ≤ ''a'' ≤ 3
| |
| − | :0 ≤ ''b'' ≤ 2
| |
| − | :0 ≤ ''c'' ≤ 1
| |
| − | の範囲に限られるということである。例えば
| |
| − | :(''a'', ''b'', ''c'') = (0, 0, 0) のとき 2<sup>0</sup> × 3<sup>0</sup> × 5<sup>0</sup> = 1
| |
| − | :(''a'', ''b'', ''c'') = (1, 0, 0) のとき 2<sup>1</sup> × 3<sup>0</sup> × 5<sup>0</sup> = 2
| |
| − | :(''a'', ''b'', ''c'') = (1, 1, 0) のとき 2<sup>1</sup> × 3<sup>1</sup> × 5<sup>0</sup> = 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 個である。
| |
| − | | |
| − | == 素因数分解アルゴリズム ==
| |
| − | 正の整数 {{mvar|N}} を素因数分解するための最も単純な方法は、{{math|2}} から順に {{math|{{sqrt|''N''}}}} までの素数で割っていく方法である（{{仮リンク|Trial division|en|Trial division}}）。しかし、{{mvar|N}} が大きくなると、この方法では困難である。
| |
| − | | |
| − | 大きな {{mvar|N}} に対しては以下のような方法がある。
| |
| − | *{{mvar|ρ}}法（[[ポラード・ロー素因数分解法]]）
| |
| − | *{{math|''p'' − 1}} 法
| |
| − | *{{math|''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)
| |
| − | | |
| − | == 素元分解 ==
| |
| − | [[整域]]において素因数分解（に相当する概念）を考える問題は、[[代数学]]における古典的な問題の一つである。
| |
| − | | |
| − | 一般に[[可換環]] {{mvar|R}} においては、「割り切る」という関係を[[単項イデアル]]の包含関係により定めることができる。すなわち、{{math|''a'', ''b'' ∈ ''R''}} の生成する単項イデアル {{math|(''a'') {{=}} ''aR''}}, {{math|(''b'') {{=}} ''bR''}} に対し、{{math|(''a'') ⊃ (''b'')}} のときに {{math|''a'' {{!}} ''b''}} と書いて、{{mvar|a}} は {{mvar|b}} を割り切る、とか、{{mvar|a}} は {{mvar|b}} の約元である、とか、{{mvar|b}} は {{mvar|a}} の倍元である、などという。言い換えると、{{mvar|a}} が {{mvar|b}} を割り切るとは、{{math|''b'' {{=}} ''ac''}} を満たすような {{mvar|R}} の[[可逆元|可逆]]でも {{math|0}} でもない元 {{mvar|c}} が存在することをいう。
| |
| − | | |
| − | 可逆でも {{math|0}} でもない {{mvar|R}} の元が、2つの非可逆元の積として表せるとき、'''可約'''であるといい、そうでないとき'''[[既約元|既約]]'''であるという。単項イデアル {{math|(''p'')}} が自明でない[[素イデアル]]であるとき、{{mvar|p}} を'''[[素元]]'''という。'''素元'''は'''既約元'''であるが、一般に逆は成立しない。
| |
| − | | |
| − | === 素元分解整域 ===
| |
| − | {{Main|素元分解整域}}
| |
| − | 環 {{mvar|R}} の元を既約元の積に表すことを'''既約元分解'''、素元の積に表すことを'''素元分解'''という。既約元分解が一意であるような環を[[素元分解整域]]もしくは一意分解環という（任意の元が素元の積に表せるなら、その表し方は一意である）。有理整数全体の成す環 {{mathbf|Z}} や[[可換体|体]]上の多項式環 {{math|''K''[''x'']}} などは素元分解整域である（高校数学でいう多項式の“因数分解”とは、通常有理数体 {{mathbf|Q}} 上の一変数多項式環における素元分解のことである）。これらの環は[[ユークリッド整域]]にもなっているが、一般にユークリッド整域は[[単項イデアル整域]]であり、単項イデアル整域は素元分解整域になる。
| |
| − | | |
| − | 素元分解整域でない例として有理数体 {{mathbf|Q}} に方程式 {{math|''x''{{sup|2}} + 5 {{=}} 0}} の根を添加した[[代数体]] {{math|'''Q'''({{sqrt|−5}})}} の[[整数環]] {{math|'''Z'''[{{sqrt|−5}}]}} で {{math|6}} を既約分解することを考えてみる。整数 {{mathbf|Z}} の範囲では {{math|2 × 3}}（と同値なもの）のみであるが、{{math|'''Z'''[{{sqrt|−5}}]}} の範囲では
| |
| − | :{{math|6 {{=}} 2 × 3 {{=}} (1 + {{sqrt|−5}})(1 − {{sqrt|−5}})}}
| |
| − | と本質的に異なる2通りに既約分解される。したがって {{math|'''Z'''[{{sqrt|−5}}]}} は素元分解整域ではない。しかし、イデアルとしては {{math|(2)}}, {{math|(3)}} や {{math|(1 ± {{sqrt|−5}})}} はさらに分解できて、素イデアルの積としては一意に
| |
| − | :{{math|(6) {{=}} (2, 1 + {{sqrt|−5}}){{sup|2}}(3, 1 + {{sqrt|−5}})(3, 1 − {{sqrt|−5}})}}
| |
| − | と分解される。一般に、代数体の整数環は[[デデキント環]]であり、素イデアルの積に一意的に分解する。
| |
| − | | |
| − | このような考察は[[エルンスト・クンマー|クンマー]]の理想数の理論に始まると考えられる。クンマー以降、[[リヒャルト・デーデキント|デデキント]]の[[イデアル|イデアル論]]などを経て[[代数的整数論]]の基盤となっている。
| |
| − | | |
| − | == 素因数分解の記録 ==
| |
| − | Cunningham Project とは、{{math2|''b'' {{=}} 2, 3, 5, 6, 7, 10, 11, 12}} および多くの自然数 {{mvar|n}} に対し、{{math|''b{{sup|n}}'' ± 1}} を素因数分解しよう、というプロジェクトである。RSA チャレンジについては[[RSA暗号#RSA暗号解読コンテスト ]]を参照。
| |
| − | *2005年4月：{{math|11{{sup|281}} + 1}} の約数として現れる176桁の合成数が素因数分解される（{{仮リンク|一般数体ふるい法|en|General number field sieve}}、[[立教大学]]、[[日本電信電話|NTT]]、富士通研究所<!-- 、世界記録 -->）<!-- 人名に統一すべきか？ -->
| |
| − | *2005年5月：200桁の合成数 RSA-200（RSAチャレンジ）が素因数分解される（一般数体ふるい法、Bahr, Boehm, Franke, Kleinjung<!--、世界記録 -->）[http://www.rsa.com/rsalabs/node.asp?id=2879]
| |
| − | *2006年8月：{{math|10{{sup|381}} + 1}} から67桁の素数が分解される（[[楕円曲線]]法、B. Dodson）
| |
| − | *2006年9月：{{math|7{{sup|352}} + 1}} の約数として現れる128桁の合成数が素因数分解される（一般数体ふるい法、[[情報通信研究機構]]、[[富士通]]、富士通研究所、[[FPGA|フィールドプログラマブルゲートアレイ]]および[[動的再構成|ダイナミックリコンフィギュラブルプロセッサ]]を用いた専用ハードウェアを初めて使用）
| |
| − | *2007年5月：{{math|2{{sup|1039}} − 1}} の約数として現れる307桁の[[合成数]]が素因数分解される（特殊数体ふるい法、NTT、ドイツのボン大学、スイス連邦工科大学との共同研究<!-- K.Aoki+J.Franke+T.Kleinjung+A.K.Lenstra+D.A.Osvik -->）
| |
| − | *20??年: 200桁（663ビット）
| |
| − | *2010年1月：232桁（768[[ビット]]）（NTT、[[スイス連邦工科大学]]ローザンヌ校 (EPFL)、独[[ボン大学]]、フランス国立情報学自動制御研究所 (INRIA)、オランダ国立情報工学・数学研究所 (CWI)。一般数体ふるい法。300台PCの[[並列計算処理]]。約3年）
| |
| − | | |
| − | == 関連項目 ==
| |
| − | *[[素因数]]
| |
| − | *[[約数]]
| |
| − | *[[公約数]]
| |
| − | *[[算術の基本定理]]
| |
| − | *[[倍数]]
| |
| − | *[[約数関数]]
| |
| − | *[[公開鍵暗号]]
| |
| − | *[[イデアル]]
| |
| − | *[[代数体]]
| |
| − | *[[デデキント環]]
| |
| − | | |
| − | == 注釈 ==
| |
| − | {{reflist}}
| |
| − | | |
| − | == 参考 ==
| |
| − | {{参照方法|date=2016年2月|section=1}}
| |
| − | * [[和田秀男]]、『コンピュータ素因子分解』、[[遊星社]]、1987、改訂版 1999、ISBN 978-4795268890
| |
| − | * 和田秀男、『素数全書－計算からのアプローチ』（訳書、R.Crandall、C.Pomerance著）、[[朝倉書店]]、2010、ISBN 978-4254111286
| |
| − | * {{Cite book|和書
| |
| − | |last1 = 山本
| |
| − | |first1 = 芳彦
| |
| − | |year = 2003
| |
| − | |title = 数論入門
| |
| − | |series = 現代数学への入門
| |
| − | |publisher = 岩波書店
| |
| − | |isbn = 4-00-006878-4
| |
| − | |ref = harv
| |
| − | }}
| |
| − | | |
| − | == 外部リンク ==
| |
| − | *[http://homes.cerias.purdue.edu/~ssw/cun/ Cunningham Project]
| |
| | | | |
| | + | 任意の合成数 <i>a</i> は，有限個の素数の積として表わすことができる。このとき <i>a</i> の因数となる有限個の素数は，<i>a</i> の素因数といわれ，<i>a</i> を素因数の積の形に表わすことを，<i>a</i> を素因数分解するという。合成数は，因数の順序を無視すれば，すべてただ1通りに素因数分解することができる。この事実を素因数分解の一意性という。たとえば 315は 315＝3<sup>2</sup>×5×7 のように素因数分解される。 ([[因数分解]] ) |
| | + | |
| | + | {{テンプレート:20180815sk}} |
| | {{DEFAULTSORT:そいんすうふんかい}} | | {{DEFAULTSORT:そいんすうふんかい}} |
| | [[Category:数論アルゴリズム]] | | [[Category:数論アルゴリズム]] |
| | [[Category:初等数学]] | | [[Category:初等数学]] |
| | [[Category:数学に関する記事]] | | [[Category:数学に関する記事]] |