Fermat primality test is used to check whether the given number is prime or not. It is a probabilistic algorithm to check the primality of a number. The Fermat primality test is based on Fermat's little theorem. The theorem is stated below.
Fermat's little theorem states that if p is a prime number and 1≤ a <p then, ap-1 ≡ 1 (mod p).
If we want to test if p is prime, then pick random number a in the interval 1≤a<p 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 probably a prime number. Fermat primality test will show Carmichael Numbers as prime numbers, even though they are composite. Carmichael numbers are also called Fermat pseudo primes because they will pass the Fermat test for primality. More over it is widely believed that there are infinitely many Carmichael numbers (At least Paul Erdos believed so), there for Fermat primality test is not highly reliable.
If we want to test if p is prime, then pick random number a in the interval 1≤a<p 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 probably a prime number. Fermat primality test will show Carmichael Numbers as prime numbers, even though they are composite. Carmichael numbers are also called Fermat pseudo primes because they will pass the Fermat test for primality. More over it is widely believed that there are infinitely many Carmichael numbers (At least Paul Erdos believed so), there for Fermat primality test is not highly reliable.
Click here to download the C Program for Fermat Primality Test.
Click here to download the C++ Program for Fermat Primality Test.
Click here to download the C++ Program for Fermat Primality Test.
No comments:
Post a Comment