Implementing primality test in Java using BigInteger

Question

I am trying to implement either the Fermat, Miller-Rabin, or AKS algorithm in Java using the BigInteger class.

I think I have the Fermat test implemented except that the BigInteger class doesn't allow taking BigIntegers to the power of BigIntegers (one can only take BigIntegers to the power of primitive ints). Is there a way around this?

The problematic line is denoted in my code:

public static boolean fermatPrimalityTest(BigInteger n)
{
    BigInteger a;
    Random rand = new Random();
    int maxIterations = 100000;

    for (int i = 0; i < maxIterations; i++) {
        a = new BigInteger(2048, rand);

        // PROBLEM WITH a.pow(n) BECAUSE n IS NOT A BigInteger
        boolean test = ((a.pow(n)).minus(BigInteger.ONE)).equals((BigInteger.ONE).mod(n));

        if (!test)
            return false;
    }

    return true;
}

Thanks for any direction!

Answer 1

I think BigInteger.modPow might be what you're looking for. Note the "mod m" in Fermat's test.

Answer 2

You'll have to implement your own pow() method. Look at the sources of BigInteger.pow() as a starting point.

Answer 3

One of the primality tests is built into BigInteger.isProbablePrime(). Not sure which one, you'd have to look at the source.

Also, you can raise a number to a power by multiplying. For example: 2^100 = 2^50 * 2^50. So pull out pieces of your BigInteger power and loop until you've used it up. But are you sure you don't mean to use BigInteger.modPow(), which takes BigIntegers? It looks like you are, based on your test.