Fermat's little theorem, a Probabilistic test for Primality

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Prime numbers hold a special place in the real world and determining if a number is a prime or not is an important algorithmic task.

Determining if a large number is prime or not is one of the most typical questions asked in the world of algorithms and competitive programming. There are several methods available to do this, but these can be broadly categorised into two:

deterministic algorithms
probabilistic algorithms

Probabilstic algorithms determines if a number is prime or not with a high probability, but it is not 100% accurate. Deterministic algorithms can conclusively check if a number is prime or not, but typically requires much higher time complexity than probabilisitc algorithms.

One of the most popular probabilistic algorithm is based on Fermat's little theorem.

Fermat's little theorem

Fermat's little theorem states that, for any prime number n, a^n-1mod(n) = 1 for 1 ≤ a <n.

For example, for n=103, if the randomly selected a is 73, 73¹⁰² % 103 is equal to 1. This is true for any number between 1 and 103.

Since this condition can also be satisfied by non-prime numbers, we run this condition k times with a randomly selected a each time. The higher the value of k, the higher the accuracy.

Pseudocode

Get N and set a value for k (more the value of k, the better)
for i from 1 to k
    a = random(2, N-1) // get a random number between 2 and N-1
    if (power(a, N-1) % N) != 1:
       return False // not a prime (100% sure)
return True // N is a prime with high probability

Complexity

Time complexity: O(K log N)

where N is the input number and K is the number of iterations

log(n) is the time complexity for computing a^n-1, and the algorithm is repeated k times, so the time complexity of this algorithm is O(klog(n)).

Example

For n=103 and k=4,

Pass 1:
Let the randomly generated number be 99

99¹⁰²%103 = 1, satisfying Fermat's theorem.

Pass 2:
Let the randomly generated number be 28

28¹⁰²%103 = 1, satisfying Fermat's theorem.

Pass 3:
Let the randomly generated number be 57

57¹⁰²%103 = 1, satisfying Fermat's theorem.

Pass 4:
Let the randomly generated number be 12

12¹⁰²%103 = 1, satisfying Fermat's theorem.

Therefore, with a high degree of accuracy we can say that the number 103 is prime.

Implementation

from random import randint

def pow(x, y, z):
    num = 1
    while y:
        if y & 1:
            num = num * x % z
        y >>= 1
        x = x * x % z
    return number
    
def isPrime(n, k=10):
    if n <= 1:
        return False
    if n <= 3:
        return True
    for i in range(k):
        a = randint(2, n - 1)
        if pow(a, n - 1, n) != 1:
            return False
    return True


if __name__ == "__main__":
    if isPrime(103):
        print("Prime")
    else:
        print("Not prime")

Limitation

This test only completely fails in the case of Carmichael numbers

Carmichael numbers are composite numbers which satisfy Fermat's theorem. Hence, the Fermat primality test returns true for these numbers despite them being composite. There are infinitely many Carmichael numbers, with the smallest being 561.

As numbers become larger, Carmichael numbers become increasingly rare. For all other numbers, provided a high enough value of k, it should return the correct answer with a high probability.