因数分解

ysd@KLab > 因数分解

因数分解の手法

計算時間が(小さい方の)素因数の大きさに依存する系
1. 試し割り法
2. 平方差分法
3. ρ法(モンテ・カルロ法)
4. p-1法
5. p+1法
6. 楕円曲線法
計算時間が合成数の大きさに依存する系
1. 二次篩法(QS)
2. 数体篩法(NFS)
3. 複数基底多項式篩法(MBPS)