algorithm - 最快的整数分解算法是什么？

Question

我编写了一个程序来尝试寻找友好配对。这需要找到数字的适当约数的总和。

这是我当前的 sumOfDivisors() 方法:

int sumOfDivisors(int n)
{  
    int sum = 1;
    int bound = (int) sqrt(n);
    for(int i = 2; i <= 1 + bound; i++)
    {
        if (n % i == 0)
            sum = sum + i + n / i;
    } 
    return sum;
}

所以我需要进行大量分解，这开始成为我应用程序中的真正瓶颈。我在 MAPLE 中输入了一个巨大的数字，它分解得非常快。

什么是更快的因式分解算法？

Answer 1

直接从我对 this other question 的回答中提取.

该方法会起作用，但会很慢。 “你的数字有多大？”确定要使用的方法:

• 小于 2^16 左右:查找表。
• 小于 2^70 左右:Richard Brent's modification的 Pollard's rho algorithm .
• 小于 10^50:Lenstra elliptic curve factorization
• 小于 10^100:Quadratic Sieve
• 大于 10^100:General Number Field Sieve