素因数分解

素因数分解 (そいんすうぶんかい、) とは、ある正の整数を素数の積の形で表すことである。
素因数分解には次のような性質がある。
例えばformula_1を素因数分解すれば、formula_2となる。
インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。
通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。
素因数分解アルゴリズム.
正の整数 を素因数分解するための最も単純な方法は、 から順に までの素数で割っていく方法（試し割り法）である。しかし、 が大きくなると、この方法では困難である。
大きな に対しては以下のような方法がある。
素元分解.
整域において素因数分解（に相当する概念）を考える問題は、代数学における古典的な問題の一つである。
一般に可換環 においては、「割り切る」という関係を単項イデアルの包含関係により定めることができる。すなわち、 の生成する単項イデアル , に対し、 のときに と書いて、 は を割り切る、とか、 は の約元である、とか、 は の倍元である、などという。言い換えると、 が を割り切るとは、 を満たすような の可逆でも でもない元 が存在することをいう。 
可逆でも でもない の元が、2つの非可逆元の積として表せるとき、可約であるといい、そうでないとき既約であるという。単項イデアル が自明でない素イデアルであるとき、 を素元という。素元は既約元であるが、一般に逆は成立しない。
素元分解整域.
環 の元を既約元の積に表すことを既約元分解、素元の積に表すことを素元分解という。既約元分解が一意であるような環を素元分解整域もしくは一意分解環という（任意の元が素元の積に表せるなら、その表し方は一意である）。有理整数全体の成す環 や体上の多項式環 などは素元分解整域である（高校数学でいう多項式の“因数分解”とは、通常有理数体 上の一変数多項式環における素元分解のことである）。これらの環はユークリッド整域にもなっているが、一般にユークリッド整域は単項イデアル整域であり、単項イデアル整域は素元分解整域になる。
素元分解整域でない例として有理数体 に方程式 の根を添加した代数体 の整数環 で を既約分解することを考えてみる。整数 の範囲では （と同値なもの）のみであるが、 の範囲では
と本質的に異なる2通りに既約分解される。したがって は素元分解整域ではない。しかし、イデアルとしては , や はさらに分解できて、素イデアルの積としては一意に
と分解される。一般に、代数体の整数環はデデキント環であり、素イデアルの積に一意的に分解する。
このような考察はクンマーの理想数の理論に始まると考えられる。クンマー以降、デデキントのイデアル論などを経て代数的整数論の基盤となっている。
素因数分解の記録.
Cunningham Project とは、 および多くの自然数 に対し、 を素因数分解しよう、というプロジェクトである。RSA チャレンジについてはRSA暗号#RSA暗号解読コンテスト を参照。
多項式時間で解いた記録.
多項式時間で解かれた記録は以下である（全て量子コンピュータによる記録である。）。