大きな数の因数分解の複雑さを見つけようとしています。最良のアルゴリズムはどれですか、そして数の素因数を見つけることの複雑さはどれですか？数の長さがnであると仮定します。
12258 次
2 に答える
1
100桁より大きい整数を因数分解するための最もよく知られているアルゴリズムは、一般的な数体ふるいです。その複雑さは、リンクがリンクしているページで説明されています。
ウィキペディアには、他のアルゴリズムに関するすばらしい記事があります：http: //en.wikipedia.org/wiki/Integer_factorization
于 2012-05-12T13:46:48.287 に答える
0
複雑さはsqrt（n）log（n）になります。ただし、n <= 19 ^ 7の場合、ふるいを使用すると、ふるいの後にlog（n）で実行できます。あなたはここで見ることができます-> http://codeforces.com/blog/entry/7262
于 2015-05-12T18:19:39.653 に答える