素因数分解アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/15 02:42 UTC 版)
「素因数分解」の記事における「素因数分解アルゴリズム」の解説
正の整数 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)
※この「素因数分解アルゴリズム」の解説は、「素因数分解」の解説の一部です。
「素因数分解アルゴリズム」を含む「素因数分解」の記事については、「素因数分解」の概要を参照ください。
ウィキペディア小見出し辞書の「素因数分解アルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 素因数分解アルゴリズムのページへのリンク
