Implementation of Fermat's primality test in Java

Question

Who wants to help me with my homework?

I'm try to implement Fermat's primality test in Java using BigIntegers. My implementation is as follows, but unfortunately it doesn't work. Any ideas?

public static boolean checkPrime(BigInteger n, int maxIterations)
{
    if (n.equals(BigInteger.ONE))
        return false;

    BigInteger a;
    Random rand = new Random();

    for (int i = 0; i < maxIterations; i++)
    {
        a = new BigInteger(n.bitLength() - 1, rand);
        a = a.modPow(n.subtract(BigInteger.ONE), n);

        if (!a.equals(BigInteger.ONE))
            return false;
    }

    return true;
}

I'm new to BigIntegers.

Thanks!

Answer 1

a should be "pick a randomly in the range (1, n − 1]" and I don't really see that happening. You could print a to check that.

As for how to do that:

BigInteger a = BigInteger.valueOf(random.nextInt(n-2)+2);

e.g. You shouldn't use the BigInteger constructor with a Random argument; that's just a source of randomness, but a should be a random value.

The 'random.nextInt(n-1)+1' comes from the definition of nextInt which, given argument k, returns a random value 0 up to and including k-1. And you want a to be larger than 1 and smaller than n.

Answer 2

Your use of the particular BigInteger constructor is reasonable, but you should use a rejection method to select a fermat base a. Here is a slight modification of your method in a class which also uses exactly one Random object:

import java.math.BigInteger;
import java.util.Random;

public class FermatTestExample
{

    private final static Random rand = new Random();

    private static BigInteger getRandomFermatBase(BigInteger n)
    {
        // Rejection method: ask for a random integer but reject it if it isn't
        // in the acceptable set.

        while (true)
        {
            final BigInteger a = new BigInteger (n.bitLength(), rand);
            // must have 1 <= a < n
            if (BigInteger.ONE.compareTo(a) <= 0 && a.compareTo(n) < 0)
            {
                return a;
            }
        }
    }

    public static boolean checkPrime(BigInteger n, int maxIterations)
    {
        if (n.equals(BigInteger.ONE))
            return false;

        for (int i = 0; i < maxIterations; i++)
        {
            BigInteger a = getRandomFermatBase(n);
            a = a.modPow(n.subtract(BigInteger.ONE), n);

            if (!a.equals(BigInteger.ONE))
                return false;
        }

        return true;
    }

    public static void main(String[] args)
    {
        System.out.printf("checkprime(2) is %b%n", checkPrime(BigInteger.valueOf(2L), 20));
        System.out.printf("checkprime(5) is %b%n", checkPrime(BigInteger.valueOf(5L), 20));
        System.out.printf("checkprime(7) is %b%n", checkPrime(BigInteger.valueOf(7L), 20));
        System.out.printf("checkprime(9) is %b%n", checkPrime(BigInteger.valueOf(9L), 20));
    }
}