Fermat primality test

Question

I have tried to write a code for Fermat primality test, but apparently failed. So if I understood well: if p is prime then ((a^p)-a)%p=0 where p%a!=0. My code seems to be OK, therefore most likely I misunderstood the basics. What am I missing here?

private bool IsPrime(int candidate)
    {
        //checking if candidate = 0 || 1 || 2
        int a = candidate + 1; //candidate can't be divisor of candidate+1
        if ((Math.Pow(a, candidate) - a) % candidate == 0) return true;
        return false;
    }

Answer 1

Reading the wikipedia article on the Fermat primality test, You must choose an a that is less than the candidate you are testing, not more.

Furthermore, as MattW commented, testing only a single a won't give you a conclusive answer as to whether the candidate is prime. You must test many possible as before you can decide that a number is probably prime. And even then, some numbers may appear to be prime but actually be composite.

Answer 2

Your basic algorithm is correct, though you will have to use a larger data type than int if you want to do this for non-trivial numbers.

You should not implement the modular exponentiation in the way that you did, because the intermediate result is huge. Here is the square-and-multiply algorithm for modular exponentiation:

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e%2 == 1
            x, e := (x*b)%m, e-1
        else b, e := (b*b)%m, e//2
    return x

As an example, 437^13 (mod 1741) = 819. If you use the algorithm shown above, no intermediate result will be greater than 1740 * 1740 = 3027600. But if you perform the exponentiation first, the intermediate result of 437^13 is 21196232792890476235164446315006597, which you probably want to avoid.

Even with all of that, the Fermat test is imperfect. There are some composite numbers, the Carmichael numbers, that will always report prime no matter what witness you choose. Look for the Miller-Rabin test if you want something that will work better. I modestly recommend this essay on Programming with Prime Numbers at my blog.

Answer 3

You are dealing with very large numbers, and trying to store them in doubles, which is only 64 bits. The double will do the best it can to hold your number, but you are going to loose some accuracy.

An alternative approach:

Remember that the mod operator can be applied multiple times, and still give the same result. So, to avoid getting massive numbers you could apply the mod operator during the calculation of your power.

Something like:

private bool IsPrime(int candidate)
{
    //checking if candidate = 0 || 1 || 2
    int a = candidate - 1; //candidate can't be divisor of candidate - 1

    int result = 1;
    for(int i = 0; i < candidate; i++)
    {
        result = result * a;

        //Notice that without the following line, 
        //this method is essentially the same as your own.
        //All this line does is keeps the numbers small and manageable.
        result = result % candidate;
    }

    result -= a;
    return result == 0;
}