From Wikipedia, the free encyclopedia:
In number theory, Fermat’s little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as:
If one wants to test whether p is prime, then we can pick random integers a and see whether the congruence holds. If it does not hold for a value of a, then p is composite. This congruence is unlikely to hold for a random a if p is composite. Therefore, if the equality does hold for one or more values of a, then we say that p is probably prime.
Please write a probabilistic program based on Fermat’s little theorem checking if a given number is prime. Use “random” function, which returns a random number from zero to n – 1, e.g. (random 5) may return 0, 1, 2, 3, or 4. Please, write also the standard deterministic program based on the well-known definition:
A prime number is a number that can only be divided by itself and 1 without remainders.
Let’s assume that 100 Fermat’s tests is enough to be sure if the number is prime. Which program is theoretically better and which performs better in real life? Can you guess why?