1

我正在尝试获取 64 位整数（大于 32 位）的除数

我的第一种方法（对于小数）是将数字除以直到结果数为 1，计算匹配素数的数量并使用公式 (1 + P1) (1+ P2) ..*(1 + Pn) = Number除数的

例如：

24 = 2 * 2 * 2 * 3 = 2^ 3 * 3^ 1

==> ( 3 + 1)*( 1 + 1) = 4 * 2 = 8 除数

        public static long[] GetPrimeFactor(long number)
        {
            bool Found = false;
            long i = 2;
            List<long> Primes = new List<long>();
            while (number > 1)
            {
                if (number % i == 0)
                {
                    number /= i;
                    Primes.Add(i);
                    i = 1;
                }
                i++;
            }
            return Primes.ToArray();
        }

但是对于大整数，这种方法需要多次迭代。我找到了一种名为Quadratic sieve的方法来使用平方数进行因式分解。现在使用我的脚本，这会容易得多，因为数字要小得多。

我的问题是，我怎样才能实现这个二次筛？

4

1 回答 1

2

二次筛法是一种寻找大数的大因子的方法；想想 10^75，而不是 2^64。即使是简单的伪代码形式，二次筛也很复杂，如果您希望它高效，则要复杂得多。对于 64 位整数来说，这太过分了，而且会比其他专门针对如此小数字的方法慢。

如果试除法对您来说太慢，那么复杂性的下一步是 John Pollard 的 rho 方法；对于 64 位整数，您可能想尝试除以某个小的限制，也许质数小于一千，然后切换到 rho。这是找到n的单个因子的简单伪代码；在复合辅因子上重复调用它来完成分解：

function factor(n, c=1)
    if n % 2 == 0 return 2
    h := 1; t := 1
    repeat
        h := (h*h+c) % n
        h := (h*h+c) % n
        t := (t*t+c) % n
        g := gcd(t-h, n)
    while g == 1
    if g is prime return g
    return factor(g, c+1)

还有其他方法可以分解 64 位整数，但这可以帮助您入门，并且对于大多数用途来说可能已经足够了；您可以搜索 Richard Brent 的 rho 算法变体以获得适度的加速。如果你想了解更多，我在我的博客上谦虚地推荐使用素数编程的文章。

于 2015-03-23T02:37:16.347 回答