我试图找到大数分解的复杂性。哪个是最好的算法，找到一个数字的主要因素的复杂性是什么？假设数字的长度为n。
问问题
12258 次
2 回答
1
用于分解大于 100 位的整数的最知名算法是General number field sieve。它的复杂性在链接链接到的页面上进行了解释。
维基百科有一篇关于其他算法的好文章：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 回答