最快的整数分解算法是什么? [英] What is the fastest integer factorization algorithm?

问题描述

我编写了一个程序来尝试寻找友好对.这需要找到数字的真因数之和.

I've written a program that attempts to find Amicable Pairs. This requires finding the sums of the proper divisors of numbers.

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

Here is my current sumOfDivisors() method:

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 中输入了一个巨大的数字，它的分解速度非常快.

So I need to do lots of factorization and that is starting to become the real bottleneck in my application. I typed a huge number into MAPLE and it factored it insanely fast.

什么是更快的分解算法之一?

What is one of the faster factorization algorithms?

推荐答案

直接从我对 this 的回答中提取其他问题.

该方法有效，但会很慢.你的数字有多大?"确定使用的方法:

Pulled directly from my answer to this other question.

The method will work, but will be slow. "How big are your numbers?" determines the method to use:

• 小于 2^16 左右:查找表.
• 小于 2^70 左右:Richard Brent 的修改Pollard 的 rho 算法.
• 小于 10^50:Lenstra 椭圆曲线分解
• 小于 10^100:二次筛
• 超过 10^100:一般数字字段筛选

这篇关于最快的整数分解算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！