Fermat Prime Test Algorithm

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) —