素因数分解
正の整数 N を素因数分解するための最も単純な方法は、2 から順に √N までの素数で割っていく方法(試し割り法)である。しかし、N が大きくなると、この方法では困難である。
大きな N に対しては以下のような方法がある。
ρ法(ポラード・ロー素因数分解法)
p − 1 法
p + 1 法
連分数法
楕円曲線法 (ECM, Elliptic curve method)
複数多項式2次ふるい法 (MPQS, Multiple polynomial quadratic sieve)
数体ふるい法 (NFS, Number field sieve) 一般数体ふるい法 (GNFS, General number field sieve) 特殊数体ふるい法 (SNFS, Special number field sieve)