大数的质因数分解 [英] Prime factorization for big numbers

问题描述

我试图找出大数分解的复杂性.哪个是最好的算法，找出一个数的质因数的复杂度是多少?假设数字的长度是n.

I am trying to find the complexity of a factorization for big numbers. Which is the best algorithm and which is the complexity of finding a number's prime factors? Assume that the length of the number is n.

推荐答案

分解大于 100 位整数的最佳算法是 一般数字字段筛选.链接链接到的页面上解释了它的复杂性.

The best know algoritm for factoring integer larger than 100 digits is General number field sieve. It's complexity is explained on the page that the link links to.

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

Wikipedia has a nice article about other algoritms: http://en.wikipedia.org/wiki/Integer_factorization

这篇关于大数的质因数分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！