|
素因数分解 (そいんすうぶんかい、) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する〔空積を 1 とする規約のもと、1 を特別扱いする必要はない（すなわち 1 は 0 個の素数の積である）。また、素数 ''p'' の素因数分解は ''p'' であり（すなわち ''p'' は 1 個の ''p'' の積である）、"素数は素因数分解できない"という表現は''誤り''である。〕。 素因数分解には次のような性質がある。 *任意の正の整数に対して、素因数分解はただ 1 通りに決定する。（素因数分解の一意性） *素因数分解の結果から、正の約数やその個数、総和などを求めることができる。 インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。 通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。 == 例 == 360 を素因数分解する。 :360 = 23 × 32 × 51 この右辺から分かることは、360 の正の約数は :2''a'' × 3''b'' × 5''c'' の形をしていて、指数は :0 ≤ ''a'' ≤ 3 :0 ≤ ''b'' ≤ 2 :0 ≤ ''c'' ≤ 1 の範囲に限られるということである。例えば :(''a'', ''b'', ''c'') = (0, 0, 0) のとき 20 × 30 × 50 = 1 :(''a'', ''b'', ''c'') = (1, 0, 0) のとき 21 × 30 × 50 = 2 :(''a'', ''b'', ''c'') = (1, 1, 0) のとき 21 × 31 × 50 = 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 個である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「素因数分解」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Integer factorization 」があります。 スポンサード リンク
|