素因数分解アルゴリズム

大きな整数を素因数に分解する問題。困難性が RSA など公開鍵暗号の安全性根拠になっている。自作ライブラリ Prifact（Julia 実装）で各手法を実験している。

手法

• 平方差法 (Fermat / 二次篩系) — $x^2\equiv y^2(\mathrm{mod}n)$ となる非自明な $x,y$ を見つけ、$\gcd (x-y,n)$ から因数を取り出す。
• 一般数体篩法 (GNFS) — 大きな合成数に対する現実的に最速のクラスのアルゴリズム。
• 関連: Berlekamp-Massey — 線形漸化式（最短 LFSR）を復元するアルゴリズム。BCH 符号などの誤り訂正・有限体計算で用いる。

計算量と暗号

素因数分解に多項式時間の古典アルゴリズムは知られておらず、この困難性が暗号に利用される。一方 計算量クラスの観点では NP に属するが NP 完全とは考えられていない（量子計算では Shor のアルゴリズムで多項式時間）。

関連: public-key-cryptosystems / fast-fourier-transform / _moc-algorithm