CODEWITHSUNDEEP
javamathprimesbiginteger
Donald T
Donald T

Reputation: 10647

BigIntegers to the power of BigIntegers

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

Upvotes: 2

Views: 3834

Answers (3)

Jonathan
Jonathan

Reputation: 13624

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.

Upvotes: 1

Eugene Kuleshov
Eugene Kuleshov

Reputation: 31795

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

Upvotes: 0

Alan Krueger
Alan Krueger

Reputation: 4786

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

Upvotes: 5

Related Questions