Primality Testing Algorithms
Overview of Primality Testing
Primality testing involves determining whether a given number is prime. Several algorithms exist, each with different efficiency and complexity levels.
Common Primality Testing Algorithms
Algorithm |
Time Complexity |
Accuracy |
Complexity |
Trial Division |
O(โn) |
100% |
Low |
Fermat Primality Test |
O(k log n) |
Probabilistic |
Medium |
Miller-Rabin Test |
O(k logยณn) |
Probabilistic |
High |
Trial Division Method
def trial_division(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
Fermat Primality Test
import random
def fermat_test(n, k=5):
if n <= 1 or n == 4:
return False
if n <= 3:
return True
for _ in range(k):
a = random.randint(2, n - 2)
if pow(a, n - 1, n) != 1:
return False
return True
Miller-Rabin Primality Test
def miller_rabin(n, k=5):
if n <= 1 or n == 4:
return False
if n <= 3:
return True
def check(a, d, n, s):
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
return True
return False
s = 0
d = n - 1
while d % 2 == 0:
d //= 2
s += 1
for _ in range(k):
a = random.randint(2, n - 2)
if not check(a, d, n, s):
return False
return True
Algorithm Comparison Flowchart
graph TD
A[Start Primality Test] --> B{Choose Algorithm}
B --> |Simple Cases| C[Trial Division]
B --> |Probabilistic| D[Fermat Test]
B --> |Advanced| E[Miller-Rabin Test]
C --> F{Is Prime?}
D --> G{Probability of Primality}
E --> H{High Accuracy}
Practical Considerations
At LabEx, we recommend choosing the appropriate algorithm based on:
- Number size
- Required accuracy
- Computational resources
- Specific use case