algorithm - 最も高速で信頼性の高い因数分解法

Question

現在使用されている最も高速で信頼性の高い因数分解方法はどれですか? 私は
Fermat の因数分解と Pollard の rho 因数分解法を調べましたが、コード化して実装するためのより良い方法があるのではないかと考えていました。

Answer 1

ウィキペディアの記事をご確認ください。探したいものはほぼすべて揃っています: http://en.wikipedia.org/wiki/Integer_factorization

解決策は実際には数値の範囲に依存し、場合によっては数値のプロパティにも依存します。

ウィキペディアによると、100 桁前後の大きな数の場合、2 次ふるいが最適です。より大きな数の場合、一般的な数値フィールドふるいの方が優れています。

あなたはすでにポラードのローについて言及しているので、小さなケースについては話しません。これは些細なことです。