大数的质因数分解

Question

我正在尝试寻找大数分解的复杂度。 哪种算法最好？找到一个数的质因数的复杂度是多少？假设该数字的长度为n。

- user1391078

Answer 1

目前已知分解100位以上整数最好的算法是广义数域筛。该链接指向的页面详细解释了其复杂度。

维基百科有一篇关于其他算法的好文章：http://en.wikipedia.org/wiki/Integer_factorization

- Koen Peters

Answer 2

复杂度将会是sqrt(n)log(n)。但是对于n<=19^7，如果你使用筛法，那么在筛选之后可以用log(n)完成。

你可以在这里查看 -> http://codeforces.com/blog/entry/7262

- Abhishek kumar yadav