Thread: Fermat Pseudoprime problem

Fermat test base a,

problem is, how many values of a are necessary to determine the primality or compositeness of N < 1000000 excluding Carmichael numbers ?

i found, if we test with primes 2,3,5,7,11 and it will find all the primes < 1000000. so i guess we need to test at least 5 values of a?


this is actually a programming problem, and i dont think it is possible to answer without testing

You cannot determine it definitely. Even if you tested all values of , it could still be composite. But the more values of you test, the higher the probability that it is prime.
I cannot find this information on the internet anymore, but I think the probability that the number is prime is equal to , where is the number of values of tested. I cannot guarantee this is the real probability formula, but it is something in this fashion.

the problem is, the question asks to test with some a in range <1000000 excluding the carmichael. so the problem is to find out whether it is composite or prime. there is no probability of getting a carmichael becausee we remove it.

Try with 20 values of a. That should be good enough.

well, i tried 2,3,5,7,11 and it works. it gives all prime numbers...

Then everything's good, try to find the probability formula