CODEWITHSUNDEEP
javaprimes
Andrew
Andrew

Reputation: 174

Why doesn't my Fermat's primality test method work?

I'm trying to implement a method which checks any integer and returns true if it's prime using Fermat's primality test.

I divided the problem depending on whether the input is less than 40 or not. If the input is less than 40 then I apply the test for every integer up until n-1. Else, if the integer is greater than 40 then the test is applied for every integer up until 40. However, it fails for some primes. 

public static boolean isPrime (double n){
    int counter=0;
    boolean isPrime=false;
    if(n<40) {
        for (int a = 2; a < n - 1; a++) {
            if (Math.pow(a, n - 1) % n == 1) counter++;
        }

        if (counter == n - 3) isPrime = true;
    }
        else {

        for (int a = 2; a <= 40; a++) {
            if (Math.pow(a, n - 1) % n == 1) counter++;

        }
        if (counter == 39) isPrime = true;
    }
    return isPrime;
}

Is it a logical issue or something else?

Upvotes: 2

Views: 168

Answers (1)

user10316011
user10316011

Reputation:

Math.pow works on doubles and the result is only approximate. Modulo on the other hand works on ints which have a range up to a little over 2 billion, is your pow producing some numbers larger than that by any chance? (17^18 seems to be a sure bet for 19...)

So how to fix this: you can implement your own pow(a,b,n) (power modulo n) using multiplication and modulo on integers. That should work correctly. Make a function to raise a to power b using a series of multiplications, apply %n to the intermediate result after each step...

Upvotes: 2

Related Questions