java - Java 中大型 BigInteger 的更快质因数分解

Question

所以我现在正在编写java代码。我已经让它工作得很好，但是任务的重点是让它分解大数字(超过 30 位数字)。它确实做到了，但可能需要 15 分钟以上才能完成，这不太好。我的教授向我保证，我使用的算法适用于 2^70 以内的数字，并且应该在大约五分钟内完成。我一直在尝试想出一种方法来做到这一点(增加 2 而不是 1 等)，但我似乎无法真正弄清楚如何让它在不跳过某些因素的情况下移动得更快。有任何想法吗？我还认为椭圆曲线方法会更好，但他告诉我现在不要处理这个问题。

这是我的代码(ps，sqrt是我自己的函数，但我确信它正在工作):

public String factorizer(BigInteger monster){
    System.out.println("monster =" + monster); 
    String factors = "";  
    BigInteger top = maths.monsterSqrt(monster);   
    if(monster.mod(two).equals(0));
        BigInteger jump = two;
    for(BigInteger bi = two; bi.compareTo(top) <= 0; bi = bi.add(jump)){
        while(monster.mod(bi).equals(zero)){
            factors +=  "+" + bi + ""; 
            monster = monster.divide(bi); 
            jump = one; 
        }
    }
    if(monster.compareTo(BigInteger.ONE) == 1){
        factors  += "+" + monster; 
    } 
    return factors; 
} 

Answer 1

这是我通过试除进行整数分解的版本:

public static LinkedList tdFactors(BigInteger n)
{
    BigInteger two = BigInteger.valueOf(2);
    LinkedList fs = new LinkedList();

    if (n.compareTo(two) < 0)
    {
        throw new IllegalArgumentException("must be greater than one");
    }

    while (n.mod(two).equals(BigInteger.ZERO))
    {
        fs.add(two);
        n = n.divide(two);
    }

    if (n.compareTo(BigInteger.ONE) > 0)
    {
        BigInteger f = BigInteger.valueOf(3);
        while (f.multiply(f).compareTo(n) <= 0)
        {
            if (n.mod(f).equals(BigInteger.ZERO))
            {
                fs.add(f);
                n = n.divide(f);
            }
            else
            {
                f = f.add(two);
            }
        }
        fs.add(n);
    }

    return fs;
}

此代码在 essay 中进行了解释在我的博客上，其中还有 Pollard 的 rho 算法的解释，该算法可能更适合分解大整数。

顺便说一句，现在 30 位数字并不是一个特别大的因式分解问题。任何超过几秒的时间都太长了。