Java中巨大的BigIntegers更快的素数因子分解

Question

所以我现在正在研究一个java代码.我已经完全正常工作,但是任务的重点是使它分解大数(超过30位).这样做,但它可能需要15分钟才能完成,这是不行的.我的教授向我保证,我使用的算法适用于最多2 ^ 70的数字,并且应该在大约五分钟内完成.我一直试图想出办法(增加2而不是1等),但我似乎无法弄清楚如何在不跳过某些因素的情况下让它更快地移动.有任何想法吗？我还认为Elliptic Curve方法会更好,但他告诉我现在不要处理它.

这是我的代码(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;
}

这篇代码在我的博客上的一篇文章中进行了解释,其中还有对Pollard的rho算法的解释,它可能更适合分解大整数.

顺便说一下,如今30个数字并不是一个特别大的因素分解问题.任何超过几秒的东西都太长了.