素因数分解
整域において素因数分解(に相当する概念)を考える問題は、代数学における古典的な問題の一つである。
一般に可換環 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 を素元という。素元は既約元であるが、一般に逆は成立しない。
素因数分解 (そいんすうぶんかい、英: prime factorization) とは、ある正の整数を素数の積の形で表すことである。
素因数分解には次のような性質がある。
任意の正の整数に対して、素因数分解はただ1通りに決定する。
素因数分解の結果から、正の約数やその個数、総和などを求めることができる。
例えば 48 {\displaystyle 48} を素因数分解すれば、 2 4 × 3 {\displaystyle 2^{4}\times 3} となる。
インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。
通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。