# Fermat's little theorem, a Probabilistic test for Primality

#### Algorithms probabilistic algorithm prime number fermat little theorem

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, an-1mod(n) = 1 for 1 ≤ a <n.

For example, for n=103, if the randomly selected a is 73, 73102 % 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 an-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

99102%103 = 1, satisfying Fermat's theorem.

Pass 2:
Let the randomly generated number be 28

28102%103 = 1, satisfying Fermat's theorem.

Pass 3:
Let the randomly generated number be 57

57102%103 = 1, satisfying Fermat's theorem.

Pass 4:
Let the randomly generated number be 12

12102%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.