大數的素因分解

Question

我正在努力尋找大數分解的複雜性。 哪一個是最好的算法，哪一個是查找數字主要因素的複雜性？假設數字的長度是n。

Answer 1

大於100位數的因式分解的最佳已知算法是General number field sieve。它的複雜性在鏈接所鏈接的頁面上進行了解釋。

維基百科有關於其他algoritms一個很好的文章：http://en.wikipedia.org/wiki/Integer_factorization

Answer 2

的複雜性將被開方（N）的log（n），但對於n < = 19^7，如果你用篩子篩再後是可以做到的在log（n）中。 你可以在這裏看到 - >http://codeforces.com/blog/entry/7262