the fermat primality test is a probabilistic test to determine if a number is probable prime. ==concept== fermat's little theorem states that if p is prime and 1 \le a < p, then :a^{p-1} \equiv 1 \pmod{p}. if we want to test if p is prime, then we can pick random as in the interval and see if the equality holds. if the equality does not hold for a value of a, then p is composite. if the equality does hold for many values of a, then we can say that p is probable prime. it might be in our tests that we do not pick any value for a such that the equality fails. any a such that :a^{n-1} \equiv 1 \pmod{n} when n is composite is known as a fermat liar. vice versa, in this case n is called fermat pseudoprime to base a. if we do pick an a such that :a^{n-1} \not\equiv 1 \pmod{n} then a is known as a fermat witness for the compositeness of n. == example == suppose we wish to determine if n&nbsp;=&nbsp;221 is prime. randomly pick 1 â¤ a < 221, say a&nbsp;=&nbsp;38. we check the above equality and find that it holds: :a^{n-1} = 38^{220} \equiv 1 \pmod{221}. either 221 is prime, or 38 is a fermat liar, so we take another a, say 26: :a^{n-1} = 26^{220} \equiv 169 \not\equiv 1 \pmod{221}. so 221 is composite and 38 was indeed a fermat liar. ==algorithm and running time== the algorithm can be written as follows: :'inputs: n: a value to test for primality; k: a parameter that determines the number of times to test for primality :output: composite if n is composite, otherwise probably prime :repeat k times: ::pick a randomly in the range [1, n &minus; 1] ::if a^{n-1}\not\equiv1 \pmod n, then return composite :if composite is never returned: return probably prime using fast algorithms for modular exponentiation, the running time of this algorithm is o(k Ã log2n Ã log log n Ã log log log n), where k is the number of times we test a random a, and n is the value we want to test for primality. ==flaw== there are infinitely many values of n (known as carmichael numbers) for which all values of a for which gcd(a, n) = 1 are fermat liars. while carmichael numbers are substantially rarer than prime numbers,erdÃ¶s' upper bound for the number of carmichael numbers is lower than the prime number function n/log(n) there are enough of them that fermat's primality test is often not used in the above form. instead, other more powerful extensions of the fermat test, such as baillie-psw, miller-rabin, and solovay-strassen are more commonly used. in general, if n is not a carmichael number then at least half of all :a\in(\mathbb{z}/n\mathbb{z})^* are fermat witnesses. for proof of this, let a be a fermat witness and a_1, a
Modular_arithmetic Primality_tests