使用gmp有效地考虑大量因素

Question

我需要得到大数的所有素数因子,这些因子可以很容易地达到1k位.这些数字实际上是随机的,所以它应该不难.我该如何有效地做到这一点？我使用C++和GMP库.

编辑:我猜你们都误解了我.
我的意思是素数是得到数字的所有素因子.
对不起我的英语,在我的语言素数和因素是相同的:)

---

澄清(来自OP的其他帖子):

我需要的是一种使用C++和GMP(Gnu Multiple Precession lib)有效地计算(找到数字的素数因子)大数(可能达到2048位)的方法,或者更不用说任何其他方式.这些数字实际上是随机的,所以几乎没有机会难以分解,即使这个数字难以计算,我也可以重新编号(尽管不能选择).

Answer 1

一个好的开始是使用小素数的一些预过滤,比如说所有素数低于10万左右.只需尝试除以它们中的每一个(创建一个表,然后在运行时加载或将其作为代码中的静态数据).它可能看起来很慢而且很愚蠢,但如果这个数字是完全随机的,这将给你一些非常快速的因素.然后查看剩余的数字并决定下一步该做什么.如果它非常小("小"意味着什么取决于你)你可以尝试素性测试(我认为GMP中有一些东西),如果它给它一个素数,你可以在大多数情况下信任它.否则你必须进一步考虑它.

如果你的数字真的很大并且你关心性能,那么你肯定需要实现比仅仅是一个愚蠢的部门更复杂的东西.看看Quadratic Sieve(试试维基百科).它非常简单但非常强大.如果您要接受挑战,请尝试使用MPQS,这是二次筛分算法的一种变体.这个论坛是一个很好的信息来源.甚至存在您需要的工具的现有实现 - 例如参见此.

请注意,1k位的数字无论如何都是巨大的.考虑到这样的数字(即使使用MPQS或其他人),如果你是幸运的话可能需要数年,如果不是,则需要永远.我认为MPQS在大约100-400位的数字上表现良好(如果它们由两个几乎同样大的素数组成,当然这是最难的情况).

Answer 2

下面是 Java 中的示例算法（不是带有 GMP 的 C++，但转换应该非常简单）：

1. x生成位长的随机数Nbits
2. 尝试分解所有 < 100 的质因数，保留除 x 的质因数列表。
3. isProbablePrime使用 Java 的方法测试剩余因子是否为素数
4. 如果剩余的因子乘积有足够的概率是素数，我们就成功分解了 x。（停止）
5. 否则，剩余的因子乘积肯定是复合的（请参阅 isProbablePrime 文档）。
6. 当我们还有时间时，我们运行Pollard rho 算法，直到找到除数 d。
7. 如果我们没有时间，我们就失败了。（停止）
8. 我们找到了除数 d。所以我们分解出 d，将 d 的质因数添加到 x 的质因数列表中，然后转到步骤 4。

该算法的所有参数都位于程序列表的开头附近。我寻找 1024 位随机数，超时为 250 毫秒，然后继续运行程序，直到得到一个至少有 4 个质因数的数字 x（有时程序会找到一个有 1、2 或 3 个质因数的数字）第一的）。使用此参数设置，在我的 2.66Ghz iMac 上通常需要大约 15-20 秒。

Pollard 的 rho 算法并不是那么高效，但与二次筛(QS) 或通用数域筛(GNFS) 相比，它很简单 - 我只是想看看这个简单的算法是如何工作的。

为什么这有效：（尽管你们中的许多人声称这是一个难题）

显而易见的事实是，素数并不罕见。对于 1024 位数字，素数定理表示每 1024 ln 2 （= 约 710）个数字中大约有 1 个是素数。

因此，如果我生成一个随机数 x，它是素数，并且我接受概率素数检测，那么我就成功分解了 x。

如果它不是素数，但我很快分解出了几个小因子，而剩下的因子（概率上）是素数，那么我就成功分解了 x 。

否则我就会放弃并生成一个新的随机数。（OP说这是可以接受的）

大多数成功分解的数字都会有 1 个大质因数和几个小质因数。

难以分解的数字是那些具有不小的质因数和至少 2 个大质因数的数字（其中包括作为两个大数乘积的加密密钥；OP 没有提到密码学），我可以当我没时间的时候跳过它们。

package com.example;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class FindLargeRandomComposite {
    final static private int[] smallPrimes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
        31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
        73, 79, 83, 89, 97};

    final static private int maxTime = 250;
    final static private int Nbits = 1024;
    final static private int minFactors = 4;
    final static private int NCERTAINTY = 4096;

    private interface Predicate { public boolean isTrue(); }

    static public void main(String[] args)
    {
        Random r = new Random();
        boolean found = false;
        BigInteger x=null;
        List<BigInteger> factors=null;
        long startTime = System.currentTimeMillis();
        while (!found)
        {
            x = new BigInteger(Nbits, r);
            factors = new ArrayList<BigInteger>();
            Predicate keepRunning = new Predicate() {
                final private long stopTime = System.currentTimeMillis() + maxTime;
                public boolean isTrue() {
                    return System.currentTimeMillis() < stopTime;
                }
            };
            found = factor(x, factors, keepRunning);
            System.out.println((found?(factors.size()+" factors "):"not factored ")+x+"= product: "+factors);
            if (factors.size() < minFactors)
                found = false;
        }
        long stopTime = System.currentTimeMillis();
        System.out.println("Product verification: "+(x.equals(product(factors))?"passed":"failed"));
        System.out.println("elapsed time: "+(stopTime-startTime)+" msec");
    }

    private static BigInteger product(List<BigInteger> factors) {
        BigInteger result = BigInteger.ONE;
        for (BigInteger f : factors)
            result = result.multiply(f);
        return result;
    }

    private static BigInteger findFactor(BigInteger x, List<BigInteger> factors,
            BigInteger divisor)
    {
        BigInteger[] qr = x.divideAndRemainder(divisor);
        if (qr[1].equals(BigInteger.ZERO))
        {
            factors.add(divisor);
            return qr[0];
        }
        else
            return x;
    }

    private static BigInteger findRepeatedFactor(BigInteger x,
            List<BigInteger> factors, BigInteger p) {
        BigInteger xprev = null;
        while (xprev != x)
        {
            xprev = x;
            x = findFactor(x, factors, p);
        }
        return x;
    }

    private static BigInteger f(BigInteger x, BigInteger n)
    {
        return x.multiply(x).add(BigInteger.ONE).mod(n);
    }

    private static BigInteger gcd(BigInteger a, BigInteger b) {
        while (!b.equals(BigInteger.ZERO))
        {
            BigInteger nextb = a.mod(b);
            a = b;
            b = nextb;
        }
        return a;
    }
    private static BigInteger tryPollardRho(BigInteger n,
            List<BigInteger> factors, Predicate keepRunning) {
        BigInteger x = new BigInteger("2");
        BigInteger y = x;
        BigInteger d = BigInteger.ONE;
        while (d.equals(BigInteger.ONE) && keepRunning.isTrue())
        {
            x = f(x,n);
            y = f(f(y,n),n);
            d = gcd(x.subtract(y).abs(), n);
        }
        if (d.equals(n))
            return x;
        BigInteger[] qr = n.divideAndRemainder(d);
        if (!qr[1].equals(BigInteger.ZERO))
            throw new IllegalStateException("Huh?");
        // d is a factor of x. But it may not be prime, so run it through the factoring algorithm.
        factor(d, factors, keepRunning);
        return qr[0];
    }

    private static boolean factor(BigInteger x0, List<BigInteger> factors,
            Predicate keepRunning) {

        BigInteger x = x0;
        for (int p0 : smallPrimes)
        {
            BigInteger p = new BigInteger(Integer.toString(p0));
            x = findRepeatedFactor(x, factors, p);          
        }
        boolean done = false;
        while (!done && keepRunning.isTrue())
        {
            done = x.equals(BigInteger.ONE) || x.isProbablePrime(NCERTAINTY);
            if (!done)
            {
                x = tryPollardRho(x, factors, keepRunning);
            }
        }
        if (!x.equals(BigInteger.ONE))
            factors.add(x);
        return done;
    }
}