Farm Permanent Test

Question

I tried to write code for the Fermat strength criterion , but it seems to have failed. Therefore, if I understood well: if p is prime, then ((a^p)-a)%p=0 , where p%a!=0 . My code seems to be in order, so 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

After reading the Wikipedia article Ferman Permanent Test , you must choose a that is less than the candidate you selected, and not More.

Also, as MattW commented, testing just one a will not give you a definitive answer as to whether the candidate is simple. You have to check the many possible a 's before deciding that the number is probably prime. And even then, some numbers may seem simple, but actually be compound.

Answer 2

You deal with very large numbers and try to save them in two-block numbers, which is only 64 bits. The double will do everything possible to hold your number, but you will lose some accuracy.

Alternative approach:

Remember that the mod statement can be applied several times and still produce the same result. Thus, in order to avoid getting massive numbers, you could apply the mod operator while calculating the power.

Sort of:

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

Answer 3

Your basic algorithm is correct, although 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 modular exponentiation the way you did, because the intermediate result is huge. Here is a square and multiplicable 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, the intermediate result will not be more than 1740 * 1740 = 3027600. But if you first raise, the intermediate result 437 ^ 13 is 21196232792890476235164446315006597, which you probably want to avoid.

Even so, the Fermat test is imperfect. There are some compound numbers, Carmichael numbers, which will always report the main thing, no matter which 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 on my blog.