Faster prime factorization for huge BigIntegers in Java

Question

so I'm working on a java code right now. I've gotten it working totally fine, however the point of the assignment is to make it factorize big number (over 30 digits). It does that, however it can take over 15 minutes for it to do it, which is no good. My professor assures me that the algorithm I am using will work for numbers up to 2^70 and should do it in about five minutes. I have been trying to come up with a way to do it (incrementing by 2 instead of 1, etc), but I can't really seem to figure out how to get it to move quicker without skipping some factors. Any ideas? I also figured that the Elliptic Curve method would be better, but he told me to not deal with that right now.

Here is my code (ps, the sqrt is my own function but I am sure it is working):

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

Here is my version of integer factorization by trial division:

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;
}

This code is explained in an essay on my blog, where there is also an explanation of Pollard's rho algorithm, which may be more suitable for factoring big integers.

By the way, 30 digits is not a particularly big factorization problem these days. Anything more than a few seconds is too long.