時間複雑度O（2 ^（n/2））の整数分解アルゴリズムは効率的ですか？

他の因数分解アルゴリズムと比較して、時間複雑度がnビットの数値の整数分数アルゴリズムはどれくらい効率的ですかO(2^(n/2))？時間複雑度O（2 ^（n/2））の整数分解アルゴリズムは効率的ですか？

出典

2017-08-04 Morgan Gethin Barrett

で知られる人気の因数分解アルゴリズムについての詳細を読むことができます。ファクタリングアルゴリズムに関するWikipediaの記事、または公開鍵暗号に関するまともな教科書を読むと、これ以上のことがすべて説明されます。 –

あなたはO（n ^（1/2））を意味しますか？ – marvel308

いいえn％i == 0の場合、係数がiとn/iの場合、ループのiを1からn ^（1/2）まで計算することができます。 – marvel308

はい、間隔[1..sqrt(X)]からのすべての除数をチェックする簡単なアルゴリズムは、同じ複雑さO(2^(n/2))を持ちます。

Pollard's rhoアルゴリズムの複雑さはO(2^(n/4))です。これは古いアルゴリズムであり、実装が容易であり、非常に長い整数ではありません。

しかし、現代数論はより効率的なアルゴリズムを持っています。たとえば、General number field sieveまたはPollard-Strassen Algorithmです。

あなたは平方根までの一般的なトライアル部門の複雑です、そして現代のファクタリングアルゴリズムに比べてかなり劣っているwiki list

出典

2017-08-04 08:07:41 knst

Pollardのrhoは 'O（2 ^（n/4））ではなくO（2 ^（n/4）））」であり、さらにa）厳密に証明されているというよりむしろ推測されたものであり、b）決定論的アルゴリズムの悪いケースの解析ではなく、確率的アルゴリズムの実行時間であると考えられた。試行分割の複雑さにもちろん、実際には試行部門よりずっと優れています。 –

@JohnColemanはい、あなたは正しいです、 'O（2 ^（n/4））' – knst

私はタイプミスを修正しました。 –

時間複雑度O（2 ^（n/2））の整数分解アルゴリズムは効率的ですか？

答えて

関連する問題