「因数分解」とは異なります。
.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%;font-size:90%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "素因数分解"
素因数分解(そいんすうぶんかい、英: prime factorization)とは、正の整数を素数の積の形で表すことである[1]。
素因数分解には次の性質がある。
任意の正の整数に対して、素因数分解はただ1通りに決定する[1]。
素因数分解の結果から、正の約数やその個数、総和などを求めることができる。
例えば 48 を素因数分解すると 24 × 3 となる。
インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難である[2]ことと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。
通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。[要出典] 正の整数 N を素因数分解するための最も単純な方法は、2 から順に √N までの素数で割っていく方法(試し割り法)である[3]。しかし、N が大きくなると、この方法では困難である。 大きな N に対しては以下の方法がある。 整域において素因数分解(に相当する概念)を考える問題は、代数学における古典的な問題の一つである。 一般に可換環 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 に方程式 x2 + 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)2(3, 1 + √−5)(3, 1 − √−5) と分解される。一般に、代数体の整数環はデデキント環であり、素イデアルの積に一意的に分解する。
素因数分解アルゴリズム
ρ法(ポラード・ロー素因数分解法)
p − 1 法
p + 1 法
連分数法
楕円曲線法 (ECM, Elliptic curve method)
複数多項式2次ふるい法 (MPQS, Multiple polynomial quadratic sieve)
数体ふるい法 (NFS, Number field sieve)
一般数体ふるい法 (GNFS, General number field sieve)
特殊数体ふるい法
素元分解
一意分解環詳細は「一意分解環」を参照