Prime Factorization in Android

Question

I am developing a small Prime Number application for Android devices and am nearly done, however I would like some help with optimizing my factorization class.

I am still having one or two problems with some large numbers(Even Numbers) being factored within a reasonable amount of time. I won't be able to use the sieve of Eratosthenes for this particular project I think as I can only sieve up to 10 million without the app crashing on my physical device (Samsung Galaxy S4 Mini). So my work around algorithm is below. I am not sure if I can maybe make the Pollard Rho algorithm that I implemented any better.

Once I have established that the number being tested isn't prime or isn't a prime square, I quickly do trial division up to 10 000, after that if the number still isn't factored completely I use the Pollard Rho method to reduce it the rest of the way.

I want to be able to factor numbers in the range of 2 > 2^64.

This is an example of a number taking roughly 15 seconds 256332652145852

It's factorization is [2, 2, 1671053, 38348971].

Any help would be gladly appreciated.

try {
        long num = Long.valueOf(input);
        if(num == 1) {
            return "1" + " = " + input;
        } else if(num < 1) {
            return "Cannot factor a number less than 1";
        } else if(PrimeNumbers.isPrime(num) == true) {
            return result = num + " is a Prime Number.";
        } else if(isSquare(num) == true && PrimeNumbers.isPrime((long) Math.sqrt(num)) == true) {

            return result = (int) Math.sqrt(num) + "<sup><small>" + 2 + "</small></sup>" + " = " + input;

        } else {
            factors(num, pFactors);
            return result = exponentialForm(pFactors, num) + " = " + input;
        }
    } catch(NumberFormatException e) {
        return result = "Unfortunately the number entered is too large";
    }
}

public static void factors(long n, ArrayList<Long> arr) {

    long number = trialDiv(n, arr);
    if(number > 1) {
        while(true) {
            long divisor = pollard(number, 1);
            if(PrimeNumbers.isPrime(divisor) == true) {
                number /= divisor;
                arr.add(divisor);
                if(PrimeNumbers.isPrime(number) == true) {
                    arr.add(number);
                    break;
                }
            }
        }
    }
}

private static long trialDiv(long n, ArrayList<Long> arr) {

    while(n % 2 == 0) {
        n /= 2;
        arr.add((long) 2);
    }

    for(long i = 3; i < 10000; i += 2) {
        if(PrimeNumbers.isPrime(i) == true) {
            while(n % i == 0) {
                arr.add(i);
                n /= i;
            }
        }
    }
    if(PrimeNumbers.isPrime(n) == true) {
        arr.add(n);
        return 1;
    }
    return n;
}

public static long pollard(long n, long c) {

    long x = 2;
    long y = 2;
    long d = 1;

    while (d == 1) {
        x = g(x, n, c);
        y = g(g(y, n, c), n, c);
        d = gcd(Math.abs(y - x), n);
    }

    if (d == n) {
        return pollard(n, c + 1);
    } else {
        return d;
    }
}

static long g(long x, long n, long c) {
    long g = (((x * x) + c) % n);
    return g;
}

static long gcd(long a, long b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

Answer 1

Your pollard function is okay but not great. You are using Pollard's original algorithm, but it would be better to use Brent's variant. But that's probably not the source of your slow performance.

Your trial division function is slow. Checking each possible divisor for primality is very expensive, and not necessary. It doesn't matter if you divide by a composite; the division will always fail, but you don't waste the time checking primality. A better approach is wheel factorization.