什么是最快的整数分解算法? [英] 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()方法:

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?

推荐答案

直接从我的回答中拉至此其他问题.

该方法可以工作，但是会很慢. 你的人数多少?"确定要使用的方法:

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:常规数字字段筛选器

• Less than 2^16 or so: Lookup table.
• Less than 2^70 or so: Richard Brent's modification of Pollard's rho algorithm.
• Less than 10^50: Lenstra elliptic curve factorization
• Less than 10^100: Quadratic Sieve
• More than 10^100: General Number Field Sieve

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