Fermat Prime Test Algorithm is to check whether a number is prime. It is a probabilistic approach that based on the following observation.
. This is also known as ‘Fermat’s little theorem’.
It states that if p is a prime number, then for any integer a, the number a^p – a is an integer multiple of p.
If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that a^(p-1) – 1 is an integer multiple of p:
.
However, there exists numbers that are not prime (are composites) but also satisfy the above equality. We call these number psudo-prime, and it is observed that there are not many regarding to its proportion.
The Fermat Prime test is to randomly pick k numbers, and test the above equality, it fails, it is definitely not prime, and after k iterations, we can say that number is probably a prime.
The Algorithm yields a higher accuracy over a certain number of iterations, and in practice, it can be trusted and used, based on the modular exponential algorithms described [here].The following Python code prints the correct answer of prime number collections from 1 to 100 inclusive. In practice, we can generate random numbers from 2 to n – 1 inclusive.
#!/usr/bin/env python from random import * seed() def powmod(a, b, n): if b == 1: return a % n r = powmod(a, b / 2, n) r = r * r % n if (b & 1) == 1: # odd number r = r * a % n return r def probalPrime(n, s): if n <= 1: return False if n <= 3: return True for _ in xrange(s): a = randint(2, n - 1) if powmod(a, n - 1, n) != 1: return False return True for _ in xrange(1, 100): if probalPrime(_, 10): print _
References:
http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Codeforces: E. Mishap in Club
Next Post: Longest Increasing Sequence