Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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.
