使用 prime/quadratic 因式分解 (C#) 查找大整数的除数

Question

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

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

例如：

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 的方法，可以使用平方数进行因式分解。现在使用我的脚本，这会容易得多，因为数字要小得多。

我的问题是，如何实现这个二次筛？

Answer 1

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

如果试验除法对您来说太慢，下一步是复杂度更高的 John Pollard 的 rho 方法；对于 64 位整数，您可能想要尝试划分到某个小限制，也许素数小于 1000，然后切换到 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 算法变体以获得适度的加速。如果你想了解更多，我虚心推荐我博客上的文章Programming with Prime Numbers。

使用 prime/quadratic 因式分解 (C#) 查找大整数的除数

Finding number of divisors of a big integer using prime/quadratic factorization (C#)

primes

quadratic

sieve

factorization