素因数分解（そいんすうぶんかい、）とは、正の整数を素数の積の形で表すことである。
素因数分解には次の性質がある。 任意の自然数に対して、素因数分解はただ1通りに決定する。(素因数分解の一意性) 素因数分解の結果から、正の約数やその個数、総和などを求めることができる。 例えば 48 を素因数分解すると となる。
インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であるhttps://www.imes.boj.or.jp/research/papers/japanese/kk18-b1-3.pdf 1ページことと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。
通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。
素因数分解アルゴリズム 自然数 を素因数分解するための最も単純な方法は、 から順に までの素数で割っていく方法（試し割り法）であるhttps://fussy.web.fc2.com/algo/math11_factorization.htm。しかし、 が大きくなると、この方法では困難である。
大きな に対しては以下の方法がある。 法（ポラード・ロー素因数分解法） 法 法 連分数法 楕円曲線法 (ECM, Elliptic curve method) 複数多項式2次ふるい法 (MPQS, Multiple polynomial quadratic sieve) 数体ふるい法 (NFS, Number field sieve) 一般数体ふるい法 (GNFS, General number field sieve) 特殊数体ふるい法 (SNFS, Special number field sieve)
素元分解 整域において素因数分解（に相当する概念）を考える問題は、代数学における古典的な問題の一つである。
一般に可換環 においては、「割り切る」という関係を単項イデアルの包含関係により定めることができる。すなわち、 の生成する単項イデアル に対し、 のときに と書いて、 は を割り切る、とか、 は の約元である、とか、 は の倍元である、などという。言い換えると、 が を割り切るとは、 を満たす、 の可逆でも でもない元 が存在することをいう。
可逆でも でもない の元が、2つの非可逆元の積として表せるとき、可約であるといい、そうでないとき既約であるという。単項イデアル が自明でない素イデアルであるとき、 を素元という。素元は既約元であるが、一般に逆は成立しない。
一意分解環
環 の元を既約元の積に表すことを既約元分解、素元の積に表すことを素元分解という。既約元分解が一意である環を一意分解環もしくは素元分解整域という（任意の元が素元の積に表せるなら、その表し方は一意である）。有理整数全体の成す環 や体上の多項式環 などは一意分解環である（中学で学習する多項式の因数分解とは、通常有理数体 上の一変数多項式環における素元分解のことである）。これらの環はユークリッド環にもなっているが、一般にユークリッド整域は単項イデアル整域であり、単項イデアル整域は一意分解環になる。
一意分解環でない例として有理数体 に方程式 の根を添加した代数体 の整数環 で を既約分解することを考えてみる。整数 の範囲では （と同値なもの）のみであるが、 の範囲では
と本質的に異なる2通りに既約分解される。したがって は一意分解環ではない。しかし、イデアルとしては , や はさらに分解できて、素イデアルの積としては一意に
と分解される。一般に、代数体の整数環はデデキント環であり、素イデアルの積に一意的に分解する。
このような考察はクンマーの理想数の理論に始まると考えられる。クンマー以降、デデキントのイデアル論などを経て代数的整数論の基盤となっている。
素因数分解の記録 Cunningham Project とは、 および多くの自然数 に対し、 を素因数分解しよう、というプロジェクトである。RSA チャレンジについてはRSA暗号#RSA暗号解読コンテスト を参照。 2005年4月： の約数として現れる176桁の合成数が素因数分解される（、立教大学、NTT、富士通研究所） 2005年5月：200桁の合成数 RSA-200（RSAチャレンジ）が素因数分解される（一般数体ふるい法、Bahr、Boehm、Franke、Kleinjung） 2006年8月： から67桁の素数が分解される（楕円曲線法、B. Dodson） 2006年9月： の約数として現れる128桁の合成数が素因数分解される（一般数体ふるい法、情報通信研究機構、富士通、富士通研究所、フィールドプログラマブルゲートアレイおよびダイナミックリコンフィギュラブルプロセッサを用いた専用ハードウェアを初めて使用） 2007年5月： の約数として現れる307桁の合成数が素因数分解される（特殊数体ふるい法、NTT、ドイツのボン大学、スイス連邦工科大学との共同研究） 20??年: 200桁（663ビット） 2010年1月：232桁（768ビット）（NTT、スイス連邦工科大学ローザンヌ校 (EPFL)、独ボン大学、フランス国立情報学自動制御研究所 (INRIA)、オランダ国立情報工学・数学研究所 (CWI)。一般数体ふるい法。300台PCの並列計算処理。約3年）
桁数オーダーの時間で解いた記録 桁数オーダーの時間で解いた記録は次のとおり（量子コンピュータによる記録）。 2001年 - 15(=3×5)の分解に成功(IBM) 2012年 - 21(=3×7)の分解に成功(ブリストル大学) これらは Shor の素因数分解法で，素因数分解したい数 N と素な数 a について，a の位数（N を法とする整数環の乗法に関する巡回群の位数）r をQFA (Quantum Fourier Transform) により桁数オーダーの時間で計算できることに基づいているが，いずの数も 2^n - 1 (2^4 - 1 = 15) またはそのような数の因数 (21 は 2^6 - 1 = 63 の因数) であり，古典コンピュータ（普通のパソコンや簡単な論理回路）でも位数 r を n（桁数）回の繰り返しで計算できる簡易な数を対象としている．したがって，QFA の有効性を実証できたとは言い難い．
関連項目
素因数 約数 公約数 因数分解 算術の基本定理 倍数 約数関数 公開鍵暗号 イデアル 代数体 デデキント環
脚注
参考文献
外部リンク Cunningham Project izutetsuya(伊豆 哲也)：「QAOA を用いた素因数分解法について」（最終更新日 2023年05月29日）