CODEWITHSUNDEEP
javaprimes
evthim
evthim

Reputation: 157

Issue with implementation of Fermat's little therorm

Here's my implementation of Fermat's little theorem. Does anyone know why it's not working?

Here are the rules I'm following:

myCode:

int low = 2;
int high = n -1;
Random rand = new Random();

//Pick any integer a between 2 and n-1.
Double a = (double) (rand.nextInt(high-low) + low);

//compute:a^n = a mod n
Double val = Math.pow(a,n) % n;

//check whether a^n = a mod n   
if(a.equals(val)){
return "True";
}else{
return "False";
}

This is a list of primes less than 100000. Whenever I input in any of these numbers, instead of getting 'true', I get 'false'.

The First 100,008 Primes

This is the reason why I believe the code isn't working.

Upvotes: 1

Views: 1190

Answers (2)

user949300
user949300

Reputation: 15729

As the others have noted, taking the power will quickly overflow. For example, if you are picking a number n to test for primality as small as say, 30, and the random number a is 20, 20^30 = about 10^39 which is something >> 2^90. (I took the ln of 10^39).

You want to use BigInteger, which even has the exact method you want: 

public BigInteger modPow(BigInteger exponent, BigInteger m)

"Returns a BigInteger whose value is (this^exponent mod m)"

Also, I don't think that testing a single random number between 2 and n-1 will "prove" anything. You have to loop through all the integers between 2 and n-1.

Upvotes: 1

ARRG
ARRG

Reputation: 2496

In java, a double only has a limited precision of about 15 to 17 digits. This means that while you can compute the value of Math.pow(a,n), for very large numbers, you have no guarantee you'll get an exact result once the value has more than 15 digits.

With large values of a or n, your computation will exceed that limit. For example Math.pow(3, 67) will have a value of 9.270946314789783e31 which means that any digit after the last 3 is lost. For this reason, after applying the modulo operation, you have no guarantee to get the right result (example).

This means that your code does not actually test what you think it does. This is inherent to the way floating point numbers work and you must change the way you hold your values to solve this problem. You could use long but then you would have problems with overflows (a long cannot hold a value greater than 2^64 - 1 so again, in the case of 3^67 you'd have another problem.

One solution is to use a class designed to hold arbitrary large numbers such as BigInteger which is part of the Java SE API.

Upvotes: 1

Related Questions