优化素数分解算法

Question

下面是一个算法，用来找出一个给定数字N的质因数分解。我在想有没有什么方法可以让这个过程在处理超级大的数字时更快一些。我说的超级大数字是指20到35位的数字。我想尽可能让这个过程快一点。有什么好主意吗？

import time

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    divisor = 2        
    while n > 1:        
        while n % divisor == 0:
            factors.append(divisor)
            n /= divisor          
        divisor = divisor + 1
        if divisor*divisor > n:
            if n > 1: 
                factors.append(n)
            break
    return factors

#HUGE NUMBERS GO IN HERE!
start_time = time.time()
my_factors = prime_factors(15227063669158801)
end_time = time.time()
print my_factors
print "It took ", end_time-start_time, " seconds."

Answer 1

看起来这个代码没有检查除数。抱歉如果我说错了，但你怎么知道除数是不是质数呢？你的除数变量在每次循环后都加1，所以我猜它会产生很多合成数。

Answer 2

对于35位数字的因式分解，任何优化算法都无法在一般情况下解决这个问题。原因是，35位数字以下的质数数量太多，根本无法在合理的时间内列出，更别提逐个尝试去除以每个质数了。即使你想尝试，存储这些质数所需的位数也会太大。因此，你需要从通用因式分解算法的列表中选择其他算法。

不过，如果所有的质因数都足够小（比如小于10^12），那么你可以使用分段的埃拉托斯特尼筛法，或者直接在网上找到一个小于某个实际数字（比如10^12）的质数列表，然后使用这个列表，而不是自己计算质数并希望列表足够大。

Answer 3

比如，我们来列出数字100的所有质因数分解。

• 首先检查2是否是一个质因数。如果是的话，所有能被2整除的数字（比如4、6、8……一直到98）都可以去掉。
• 接着检查3，如果3是质因数，那么所有能被3整除的数字（比如9、12……一直到99）也可以去掉。
• 4已经被去掉了，因为它不是质数。
• 然后检查5，能被5整除的数字（比如10、15、20……一直到100）也都去掉。
• 6也被去掉了。
• 继续检查7，然后……

Answer 4

你的算法是试除法，这种方法的时间复杂度是 O(√n)，也就是说，随着数字 n 的增大，计算的时间会增加得比较快。你可以通过只用 2 和奇数作为试除数来改进你的算法，甚至更好的是，只用质数作为试除数，但时间复杂度还是 O(√n)。

如果想要更快，你需要一个更好的算法。试试这个：

def factor(n, c):
    f = lambda(x): (x*x+c) % n
    t, h, d = 2, 2, 1
    while d == 1:
        t = f(t); h = f(f(h)); d = gcd(t-h, n)
    if d == n:
        return factor(n, c+1)
    return d

要在你的数字上调用它，比如说

print factor(15227063669158801, 1)

这样可以几乎瞬间返回一个（可能是合成数的）因子 2090327。这个算法叫做 rho 算法，是约翰·波拉德在 1975 年发明的。rho 算法的时间复杂度是 O(√(√n))，所以它比试除法快得多。

还有很多其他的整数因式分解算法。对于你感兴趣的 20 到 35 位数字，椭圆曲线算法非常合适。它应该能在几秒钟内分解这样的数字。另一个适合这种数字的算法，特别是对于半质数（只有两个质因子的数），是 SQUFOF。

如果你对质数编程感兴趣，我推荐你看看我博客上的 这篇文章。看完之后，我博客上还有关于椭圆曲线因式分解、SQUFOF 以及其他更强大的因式分解方法的内容。