素因数分解

素因数分解（そいんすうぶんかい）とは、ある正の整数を素数の積の形で表す方法のことである。ただし、1 に対する素因数分解は 1 と定義する。

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

任意の正の整数に対して、素因数分解はただ 1 通りに決定する。（ただし、順序は問わない。）
素因数分解の結果を利用して、約数や約数の総和などを導き出す事が出来る。

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

例

360 を素因数分解する。

360 = 2³ × 3² × 5¹

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

2^a × 3^b × 5^c

の形をしていて、指数は

0 ≤ a ≤ 3

0 ≤ b ≤ 2

0 ≤ c ≤ 1

の範囲に限られるということである。例えば

(a,b,c)=(0,0,0)にあたる 360 の約数は 2⁰ × 3⁰ × 5⁰ = 1

(a,b,c)=(1,0,0)にあたる 360 の約数は 2¹ × 3⁰ × 5⁰ = 2

(a,b,c)=(1,1,0)にあたる 360 の約数は 2¹ × 3¹ × 5⁰ = 6

などのように表せる。

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

素因数分解の方法

正の整数 n を素因数分解するための最も単純な方法は、 2 から順に √n までの素数で割っていく方法である。しかし、n が大きくなると、この方法では困難である。

大きな n に対しては以下のような方法がある。

ρ法
p-1法
p+1法
連分数法
楕円曲線法(ECM)
複数多項式2次ふるい法(MPQS)
数体ふるい法(NFS)

素元（既約元）分解

一般に環構造を持った集合 R においては "割り切る" という関係を単項イデアルの包含関係により定めることができる。すなわち、a, b ∈ R の生成する単項イデアル (a) = aR, (b) = bR について

a|b ⇔ (a) ⊃ (b)

と書いて、a は b を割り切るとか、a は b の約元であるとか、b は a の倍元であるなどとかいうわけである。これはつまり、a = bc を満たすような R の可逆でも 0 でもない元 c が存在することを a が b を割り切ると言っているのである。

R の元 p が、 R の可逆元しか約元として持たないなら既約であるといい、そうでないなら可約であるという。p が既約元であることと単項イデアル (p) が素イデアルになることとは同値である。この意味で p は素元であるということもある。

一意分解環

環 R の元を既約元の積に表すことを既約元分解、素元分解という。この表し方が一意であるような環を一意分解環あるいは素元分解環という。

多項式の因数分解

高校数学でいう "因数分解" とは体 Q 上の一変数多項式環における素元分解のことである。体上の一変数多項式環は単項イデアル整域で、単項イデアル整域は一意分解環である。

代数体の範囲における素因数分解

既約元分解としての素因数分解を代数的整数の範囲で行うとき、一意性を持たなくなることがありうる。また、整数の範囲で素数（既約元）であったものがそうでなくなることが起こりうる。

例として有理数体 Q に方程式 x² + 5 = 0 の根を添加した代数体 $\mathbb{Q}(\sqrt{-5})$ の整数環 $\mathbb{Z}$ ^* の範囲で 6 を既約分解する。

整数　Z の範囲では 2 × 3 のみしかありえないが、Z^* の範囲では

2 \times 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}) = 6

という二通りの既約分解が可能になる。しかしながら、イデアルとしては (2), (3) や (1 ± √-5) はさらに分解できて、素イデアルの積としては一意的に

(6) = (2, 1 + \sqrt{-5})^2 (3, 1 + \sqrt{-5})(3, 1 - \sqrt{-5})

と分解される。

このような考察はクンマーの理想数の理論に始まると考えられる。クンマー以降、デデキントのイデアル論などを経て可換環論の基盤となっている。(see also イデアル)

Gourt Home::Gourt :: 素因数分解

例

素因数分解の方法

素元（既約元）分解

一意分解環

多項式の因数分解

代数体の範囲における素因数分解

関連項目