素因数分解

素因数分解 (そいんすうぶんかい、: prime factorization) とは、ある正の整数素数の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する[1]

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

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

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

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

360 を素因数分解する。

360 = 23 × 32 × 51

この右辺から分かることは、360 の正の約数

2a × 3b × 5c

の形をしていて、指数

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 個である。

他の言語で