Fermat Primality Test: Complete Mathematical Guide

1. Introduction and Core Concepts

The fermat primality test is one of the oldest and most elegant probabilistic algorithms for determining whether a given number is likely to be prime. Named after Pierre de Fermat and his celebrated Little Theorem, the test provides a fast, practical method to filter composite numbers with high confidence without performing expensive deterministic factorization. Unlike trial division, which becomes infeasible for large integers, the fermat primality test leverages modular exponentiation to achieve polylogarithmic time complexity, making it indispensable in modern cryptography and computational number theory.

At its heart, the fermat primality test answers a simple question: is the number n probably prime or definitely composite? It is crucial to understand that the test is probabilistic, not deterministic. If the test declares a number composite, it is 100% correct. If it declares a number probably prime, there remains a small probability of error. This one-sided error property classifies it as a Monte Carlo algorithm. For many practical applications, especially when combined with multiple iterations, this error probability can be made negligibly small.

The importance of the fermat primality test stems from the fundamental role of prime numbers in computer science. Large primes are the foundation of public-key cryptosystems such as RSA, Diffie-Hellman, and elliptic curve cryptography. Generating a 2048-bit RSA key requires finding two large probable primes quickly. Testing each candidate with a deterministic method like the AKS primality test would be far too slow for production use. The fermat primality test, and its more robust descendants, provides the speed necessary to make secure communication on the web, in databases, and across networks feasible at scale.

What Defines a Primality Test?

A primality test is any algorithm that determines whether an input number is prime. Tests are broadly categorized as deterministic, which always give a correct answer, and probabilistic, which may give a false positive. The fermat primality test falls into the latter category. A number that passes the test is called a Fermat probable prime or Fermat pseudoprime to a given base, while a composite number that passes for all bases coprime to it is known as a Carmichael number, which represents the key limitation of the test.

Why Fermat Matters Today

Despite being superseded by more accurate tests like Miller-Rabin for critical applications, understanding the fermat primality test is essential for every computer scientist. It introduces the core concepts of modular arithmetic, probabilistic analysis, and pseudoprimes that underpin all modern primality testing. Its simplicity and speed also make it an excellent first filter in prime generation pipelines, where it can quickly eliminate the vast majority of composites before a more expensive test is applied.

2. How It Works

The entire mechanism of the fermat primality test rests on Fermat's Little Theorem, a cornerstone of number theory. The theorem states that if p is a prime number and a is any integer such that 1 < a < p and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p). In other words, raising any base coprime to a prime to the power of one less than the prime will always leave a remainder of 1 when divided by that prime.

The test inverts this logic to create a compositeness test. Given an odd integer n that we wish to test, we choose a random base a in the range [2, n-2]. We then compute a^(n-1) mod n. If the result is not equal to 1, then by the contrapositive of Fermat's Little Theorem, n cannot be prime and is definitively composite. In this case, a is called a Fermat witness for the compositeness of n. If the result is 1, then n is said to be a probable prime to base a, and a is called a Fermat liar.

A single base is not enough to be confident. A composite number may have many bases for which it falsely appears prime. These are called Fermat pseudoprimes. For example, 341 = 11 × 31 is composite, but 2^340 ≡ 1 (mod 341), so it is a pseudoprime to base 2. To reduce the error, the test is repeated with k independently chosen random bases. If n passes all k rounds, the probability that it is composite drops exponentially. For most composite numbers, at least half of the bases in [2, n-2] will be witnesses, giving an error probability of at most (1/2)^k.

The Carmichael Number Problem

The Achilles' heel of the fermat primality test is the existence of Carmichael numbers. These are composite numbers n that satisfy a^(n-1) ≡ 1 (mod n) for every base a that is coprime to n. The smallest Carmichael number is 561 = 3 × 11 × 17. For such numbers, the Fermat test will always declare them probably prime, regardless of how many bases coprime to n are tested. There are infinitely many Carmichael numbers, though they are rare. This limitation is why production cryptographic libraries never rely solely on the Fermat test and instead use Miller-Rabin or Baillie-PSW.

Modular Exponentiation

The computational engine of the test is modular exponentiation: computing a^(n-1) mod n efficiently. Directly computing a^(n-1) is impossible for large n (e.g., 1024-bit numbers) because the intermediate result would have billions of digits. Instead, the algorithm uses repeated squaring, also known as binary exponentiation, which keeps all intermediate values smaller than n^2 and runs in O(log n) multiplications. This efficiency is what makes the fermat primality test practical.

3. Implementation

Implementing the fermat primality test correctly requires attention to edge cases, efficient modular arithmetic, and proper random base selection. Python's built-in three-argument pow(base, exp, mod) function provides a highly optimized, constant-time modular exponentiation implemented in C, which should always be preferred over a naive implementation for performance and security.

The following examples demonstrate the progression from a basic implementation to a production-aware version. Note that all code is written for clarity and educational purposes, with detailed comments explaining each step.

def mod_pow(base, exponent, modulus):
    """
    Efficient modular exponentiation using binary exponentiation.
    Computes (base^exponent) % modulus in O(log exponent) time.
    """
    result = 1
    base = base % modulus
    while exponent > 0:
        # If exponent is odd, multiply result by base
        if exponent % 2 == 1:
            result = (result * base) % modulus
        # Square the base and halve the exponent
        exponent = exponent >> 1
        base = (base * base) % modulus
    return result

def fermat_single_base(n, a):
    """
    Single round of Fermat test with base a.
    Returns True if n is probable prime to base a, False if composite.
    """
    if n <= 1:
        return False
    if n <= 3:
        return True  # 2 and 3 are prime
    if n % 2 == 0:
        return False
    # Fermat's Little Theorem check: a^(n-1) % n == 1 ?
    return mod_pow(a, n - 1, n) == 1

import random

def fermat_primality_test(n, k=5):
    """
    Probabilistic Fermat primality test with k rounds.
    Args:
        n: integer to test for primality (n > 2)
        k: number of random bases to try (higher k = lower error)
    Returns:
        False if n is definitely composite, True if probably prime
    """
    # Handle small numbers and even numbers
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False

    # Perform k independent rounds
    for _ in range(k):
        # Choose random base a in [2, n-2]
        a = random.randrange(2, n - 1)
        # If gcd(a, n) != 1, then n is composite (found a factor)
        # This check also prevents false positives when a and n not coprime
        # For simplicity we check via pow result; explicit gcd is optional
        if pow(a, n - 1, n) != 1:
            return False  # Definitely composite, a is a witness
    return True  # Probably prime after k rounds

# Example usage
print(fermat_primality_test(101, k=5))   # True - 101 is prime
print(fermat_primality_test(341, k=5))   # Often True - 341 is pseudoprime to base 2
print(fermat_primality_test(561, k=10))  # Often True - 561 is Carmichael number

import math
import random

def fermat_test_with_gcd(n, k=10):
    """
    Improved Fermat test that explicitly checks gcd.
    This catches some composites faster and handles Carmichael detection better.
    """
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0:
        return False

    for _ in range(k):
        a = random.randrange(2, n - 1)
        g = math.gcd(a, n)
        if g != 1:
            return False  # Found non-trivial divisor, definitely composite
        # Use Python's built-in fast modular exponentiation
        if pow(a, n - 1, n) != 1:
            return False
    return True

def generate_probable_prime(bits, k=10):
    """
    Generate a probable prime of specified bit length using Fermat test.
    This mimics how RSA key generation finds large primes.
    """
    while True:
        # Generate random odd number with top bit set to ensure bit length
        candidate = random.getrandbits(bits)
        candidate |= (1 << bits - 1) | 1  # Set high bit and low bit (make odd)
        if fermat_test_with_gcd(candidate, k):
            return candidate

# Generate a 64-bit probable prime (small for demo)
# prime_64 = generate_probable_prime(64, k=7)
# print(f"Generated 64-bit probable prime: {prime_64}")

def is_carmichael_number(n, trials=20):
    """
    Heuristic check for Carmichael numbers.
    Tests many bases; if all coprime bases pass, n is likely Carmichael.
    Note: This is for educational demonstration only.
    """
    import math, random
    if n < 2 or n % 2 == 0:
        return False
    # Quick check: Carmichael numbers must be square-free and composite
    # Korselt's criterion: n is Carmichael iff n is square-free and
    # for every prime p dividing n, (p - 1) divides (n - 1)
    for _ in range(trials):
        a = random.randrange(2, n)
        if math.gcd(a, n) == 1:
            if pow(a, n - 1, n) != 1:
                return False  # Found witness, not Carmichael
    # If we never found a witness among coprime bases, suspect Carmichael
    # Verify compositeness separately
    if fermat_test_with_gcd(n, k=5):
        # Could be prime or Carmichael; do trial division for small n
        for p in range(3, int(math.sqrt(n)) + 1, 2):
            if n % p == 0:
                return True  # Composite and passed all Fermat tests
    return False

# Known Carmichael numbers
test_values = [561, 1105, 1729, 2465, 2821, 6601, 8911]
for val in test_values:
    print(f"{val}: Carmichael? {is_carmichael_number(val)} | Fermat says prime? {fermat_primality_test(val, k=10)}")

4. Step-by-Step Example

To make the abstract theory concrete, let us walk through the fermat primality test manually for two numbers: a small prime n = 13 and a famous pseudoprime n = 341. We will use base a = 2 and compute 2^(n-1) mod n using repeated squaring to show every intermediate step.

First, consider n = 13, which is prime. We choose base a = 2. We need to compute 2^12 mod 13. Using binary exponentiation, we decompose the exponent 12 = 8 + 4. We compute powers of 2 modulo 13: 2^1 mod 13 = 2, 2^2 mod 13 = 4, 2^4 mod 13 = (4^2) mod 13 = 16 mod 13 = 3, 2^8 mod 13 = (3^2) mod 13 = 9. Then 2^12 = 2^8 × 2^4 mod 13 = 9 × 3 mod 13 = 27 mod 13 = 1. Since the result is 1, the test correctly reports that 13 is a probable prime to base 2. If we repeated with bases 3, 5, and 6, all would return 1, increasing our confidence.

Now consider n = 341, which is composite (341 = 11 × 31). Test with base a = 2: we need 2^340 mod 341. This looks daunting, but modular exponentiation makes it tractable. By computation, 2^10 = 1024 ≡ 1 mod 341? Let us check: 341 × 3 = 1023, so 1024 mod 341 = 1. Therefore 2^10 ≡ 1 (mod 341). Then 2^340 = (2^10)^34 ≡ 1^34 ≡ 1 (mod 341). The test returns 1, so it falsely declares 341 probably prime to base 2. This demonstrates a Fermat pseudoprime.

Second Base Exposes the Composite

If we test the same n = 341 with base a = 3, the result is different. Computing 3^340 mod 341 yields 56, not 1. Because 56 ≠ 1, base 3 is a Fermat witness that proves 341 is composite. This illustrates why multiple rounds are essential. A single round with a liar base gives a false positive, but a second round with a witness base catches the error. For non-Carmichael composites, at least 50% of bases are witnesses, so testing a few random bases makes the chance of picking only liars very small.

Walkthrough with Carmichael Number 561

Finally, test n = 561 = 3 × 11 × 17, the smallest Carmichael number, with base a = 2. Since gcd(2, 561) = 1, we compute 2^560 mod 561. By the Chinese Remainder Theorem, this is equivalent to checking modulo 3, 11, and 17 separately. 2^2 ≡ 1 mod 3, so 2^560 = (2^2)^280 ≡ 1 mod 3. Similarly, 2^10 ≡ 1 mod 11 and 560 is divisible by 10, and 2^16 ≡ 1 mod 17 is not directly helpful but 2^8 ≡ 1 mod 17? Actually 2^4 =16 ≡ -1 mod 17, so 2^8 ≡1 mod 17 and 560 mod 8 =0. In all three cases the result is 1, so by CRT, 2^560 ≡ 1 mod 561. In fact, every base coprime to 561 will yield 1, so the Fermat test can never detect that 561 is composite by testing coprime bases alone. This is the fundamental limitation that motivates stronger tests.

5. Complexity Analysis

The efficiency of the fermat primality test is dominated by the cost of modular exponentiation. Understanding its time and space complexity is critical for predicting performance when testing large integers, such as 1024-bit or 2048-bit candidates during RSA key generation.

Modular exponentiation via binary exponentiation requires O(log n) modular multiplications, where n is the number being tested. Each multiplication of numbers of size log n bits using naive grade-school multiplication costs O((log n)^2) bit operations. Therefore, a single Fermat round costs O((log n)^3) bit operations. If using more advanced multiplication algorithms like Karatsuba or FFT-based methods, the cost per multiplication drops to O((log n)^1.585) or O(log n log log n), but for typical cryptographic sizes, the cubic bound is a practical approximation. Python's built-in pow with three arguments is implemented in C using efficient algorithms and is significantly faster than a pure Python loop.

Space complexity is much more modest. The algorithm only needs to store a few integers of size O(log n) bits: the base, exponent, modulus, and intermediate result. Thus the auxiliary space is O(log n). This makes the test highly memory-efficient and suitable for embedded systems or smart cards where memory is constrained.

The number of rounds k is a tunable parameter that trades accuracy for time. Total time scales linearly with k, giving O(k × (log n)^3). Choosing k between 5 and 20 is common; each additional round halves the error probability for non-Carmichael numbers but doubles the runtime.

* Best case occurs when a small base reveals compositeness quickly or when n is even and rejected in O(1). The table uses bit complexity where n is the integer value and log n is its bit-length. In practice, wall-clock time is dominated by the pow() call, which is highly optimized.

6. Variations and Optimizations

While the basic fermat primality test is simple, several variations and optimizations improve its reliability, speed, and utility in real systems. Most production systems do not use pure Fermat alone but combine it with other techniques in a pipeline.

One common optimization is to perform trial division by small primes before invoking the Fermat test. Since a large fraction of random odd numbers are divisible by 3, 5, 7, 11, etc., quickly checking divisibility by the first 100 primes eliminates ~88% of composites in negligible time. Only numbers that survive this sieve are subjected to the more expensive modular exponentiation. This hybrid approach dramatically reduces the average cost of prime generation.

Another improvement is to use deterministic bases for numbers below certain bounds. It is known that testing bases 2, 3, 5, 7, and 11 is sufficient to correctly determine primality for all n < 3,474,749,660,383. For 32-bit integers, testing bases 2, 7, and 61 is deterministic. These fixed-base variants turn the probabilistic test into a deterministic one for bounded inputs, which is useful for competitive programming and embedded applications where the input size is limited.

From Fermat to Miller-Rabin

The most important variation is the Miller-Rabin test, which can be viewed as a strengthened Fermat test. Miller-Rabin writes n-1 as d × 2^s with d odd, then checks not only whether a^d ≡ 1 (mod n) or a^(d×2^r) ≡ -1 (mod n) for some r < s. Every Fermat witness is also a Miller-Rabin witness, but Miller-Rabin has no Carmichael-like numbers that fool all bases; for any composite n, at least 75% of bases are witnesses. This makes Miller-Rabin strictly stronger while retaining the same O(k (log n)^3) complexity.

Parallel and Batch Optimizations

For prime generation, candidates can be tested in parallel across multiple cores or machines. Since each Fermat round is independent, k rounds can be distributed. Additionally, using Montgomery multiplication or precomputed Barrett reduction can accelerate the modular multiplications by 20-30% for large integers. In hardware implementations, such as on FPGAs for cryptographic accelerators, the binary exponentiation loop is unrolled and pipelined for constant-time execution to prevent side-channel attacks.

7. Real-World Applications

Although pure fermat primality test is rarely used alone in high-assurance cryptography due to Carmichael numbers, its principles and its role as a fast pre-filter make it ubiquitous in systems that handle large numbers. Its speed and simplicity ensure it remains relevant in performance-sensitive contexts.

In cryptography, the primary application is RSA and Diffie-Hellman key generation. Web servers, such as those running OpenSSL or BoringSSL, must generate ephemeral prime parameters for TLS handshakes and for creating new certificates. A typical RSA-2048 key generation process generates random 1024-bit odd candidates, sieves out those divisible by small primes, runs a fast Fermat test with 1-2 rounds to discard obvious composites, and then applies 10-20 rounds of Miller-Rabin to the survivors. This layered approach balances throughput and security, allowing a busy server to generate keys without noticeable latency.

Databases and distributed systems also rely on primality testing for hashing and sharding. Many hash table implementations achieve better distribution when the table size is prime, reducing clustering. When a hash table needs to resize, the system must quickly find the next prime larger than twice the current capacity. A fast probabilistic test like Fermat is ideal for this, as a false positive (choosing a pseudoprime as table size) has minimal impact on performance, while speed is critical to avoid pausing database operations.

In networking, certain protocols use prime numbers for randomized backoff, port selection, or for generating unique identifiers that minimize collisions. Blockchain and cryptocurrency systems use large primes for proof-of-work variations, zero-knowledge proofs, and for generating safe primes where (p-1)/2 is also prime. While final verification uses deterministic or Miller-Rabin tests, Fermat is often used during the search phase to quickly scan millions of candidates.

Embedded and Educational Use

Beyond large-scale infrastructure, the fermat primality test is valuable in resource-constrained environments. Smart cards, IoT devices, and microcontrollers that need to generate primes for lightweight cryptography cannot afford the code size or complexity of AKS. A compact Fermat implementation with a few fixed bases provides a reasonable trade-off. In education, the test is a standard assignment in algorithms courses to teach modular arithmetic, probabilistic analysis, and the difference between Monte Carlo and Las Vegas algorithms.

8. Comparison with Alternatives

Primality testing offers a spectrum of algorithms trading off speed, accuracy, and complexity. Understanding where the fermat primality test sits in this landscape helps engineers choose the right tool for their constraints.

Trial division is the simplest deterministic method: test divisibility by all integers up to √n. While easy to implement and 100% accurate, its O(√n) time is exponential in the bit-length and becomes infeasible beyond 60-bit numbers. It is only used for sieving small factors.

The Solovay-Strassen test, like Fermat, is probabilistic but based on Euler's criterion and the Jacobi symbol. It has a provable error bound of (1/2)^k and, unlike Fermat, has no Carmichael-like numbers that fool all bases. However, computing Jacobi symbols adds overhead and its error bound is worse than Miller-Rabin's (1/4)^k, so it is now largely of historical interest.

Miller-Rabin is the modern workhorse. It strengthens Fermat by checking square roots of 1 modulo n. It has no fixed pseudoprimes that fool all bases, and for any composite, at most 1/4 of bases are liars. With k rounds, error is at most (1/4)^k, far better than Fermat's (1/2)^k for non-Carmichael numbers. Its runtime is also O(k (log n)^3), essentially identical to Fermat, making it strictly dominant for security-critical code.

The AKS primality test, discovered in 2002, is the first deterministic, polynomial-time, unconditional test with O((log n)^6) complexity. While theoretically groundbreaking, its constants are large and it is orders of magnitude slower than Miller-Rabin for cryptographic sizes. It is used when deterministic guarantees are required without relying on unproven assumptions, but rarely in production.

* For Fermat, the (1/2)^k bound applies only to non-Carmichael composites. For Carmichael numbers, error is 1 regardless of k if bases are coprime. Miller-Rabin's (1/4)^k bound holds for all composites, which is why it is preferred.

9. Common Mistakes and Best Practices

Implementing the fermat primality test seems trivial, but subtle pitfalls can lead to incorrect results, security vulnerabilities, or poor performance. Awareness of these mistakes is essential for both interview settings and production code.

A frequent mistake is forgetting to handle small numbers and even numbers as special cases. The test as defined requires n > 3 and odd. If the code does not explicitly return False for n < 2, True for n = 2 or 3, and False for even n > 2, it may incorrectly classify 1 as prime or waste time testing even numbers. Another common error is choosing bases outside the valid range [2, n-2] or reusing the same base across rounds, which does not reduce error probability.

A more serious error is ignoring the gcd check. If gcd(a, n) ≠ 1, then a and n share a factor, so n is composite. Some naive implementations compute pow(a, n-1, n) without checking gcd first. While pow will still return a value ≠ 1 in many cases, it is not guaranteed to be a witness when a and n are not coprime, and the opportunity for an early, cheap exit is missed. Always compute math.gcd(a, n) before exponentiation when robustness matters.

Performance pitfalls include implementing modular exponentiation with a Python loop and using ** instead of pow(a, n-1, n). A naive loop is not only 50-100x slower but may not be constant-time, leaking information via timing side channels in cryptographic contexts. Always use the built-in three-argument pow, which is implemented in C and uses efficient exponentiation with Montgomery reduction where available.

Best Practices Checklist

• Use a hybrid pipeline: Sieve small primes → 1-2 rounds Fermat → Miller-Rabin for survivors. Never rely on Fermat alone for security-critical primes.
• Choose k appropriately: For 64-bit numbers, k=7 gives error < 1%; for 1024-bit RSA candidates, k=10-20 is standard. More rounds are cheap compared to the cost of using a composite as a prime.
• Use cryptographically secure randomness: When generating bases for key generation, use secrets module or os.urandom, not random.randrange, to avoid predictable bases.
• Test known edge cases: Validate your implementation against known primes (2, 3, 5, 101, 2^31-1), known pseudoprimes (341, 561, 645), and Carmichael numbers (561, 1105, 1729).
• Document probabilistic nature: Clearly name functions is_probable_prime or fermat_probable_prime, not is_prime, to avoid misleading callers into assuming determinism.

Finally, remember that the fermat primality test is a compositeness test with one-sided error. If it says composite, you can trust it. If it says probably prime, you must qualify the answer with the number of rounds and the presence of Carmichael risk. In interviews and code reviews, explicitly stating this distinction demonstrates deep understanding.

10. Interview Questions

Interviewers frequently use the fermat primality test to assess understanding of number theory, probabilistic algorithms, and complexity analysis. Below are common questions with guidance on what a strong answer should cover.

Q1: Explain Fermat's Little Theorem and how it leads to the Fermat primality test. What is a Fermat witness?

Strong Answer: State the theorem precisely: if p is prime and 1 < a < p, then a^(p-1) ≡ 1 mod p. Explain the contrapositive: if a^(n-1) ≠ 1 mod n for some a coprime to n, then n is composite. Describe the algorithm: pick random a, compute pow(a, n-1, n), return composite if ≠1, otherwise probably prime. Define witness as a base that proves compositeness and liar as a base that falsely suggests primality. Mention that for non-Carmichael composites, at least half the bases are witnesses, giving error ≤ (1/2)^k. Bonus points for mentioning Carmichael numbers as the counterexample where no witness exists among coprime bases.

Q2: What is the time complexity of the Fermat test? How does k affect accuracy and performance?

Strong Answer: Single round is dominated by modular exponentiation: O(log n) multiplications, each O((log n)^2) with naive multiplication, so O((log n)^3) bit operations and O(log n) space. k rounds is O(k (log n)^3) time, linear in k. Accuracy improves exponentially: error ≤ (1/2)^k for non-Carmichael numbers, so each extra round halves error but doubles time. For Carmichael numbers error remains 1 regardless of k. Discuss trade-off: choose k=5-10 for moderate assurance, k=20 for cryptographic use, but note that Miller-Rabin gives better (1/4)^k bound for same cost.

Q3: Give an example of a composite number that passes the Fermat test to base 2. How would you detect it?

Strong Answer: Provide 341 = 11×31, where 2^340 ≡1 mod 341, so it is a pseudoprime to base 2. Explain that testing base 3 yields 3^340 ≡56 mod 341 ≠1, so base 3 is a witness. Emphasize that one base is insufficient; multiple random bases reduce chance of picking only liars. For full detection, note that Carmichael numbers like 561 pass all coprime bases, so Fermat alone cannot detect them; must use Miller-Rabin or check Korselt's criterion or perform trial division. Mention that sieving small primes would quickly find factor 11 for 341.

Q4: Compare Fermat and Miller-Rabin tests. When would you use each?

Strong Answer: Both are O(k (log n)^3) probabilistic tests, but Miller-Rabin is strictly stronger: it checks for non-trivial square roots of 1 by writing n-1 = d·2^s and testing a^d and successive squares. Every Fermat witness is a Miller-Rabin witness, but not vice versa. Miller-Rabin has no Carmichael-like numbers and error ≤ (1/4)^k vs Fermat's (1/2)^k (and failure on Carmichael). Use Fermat as a fast pre-filter or for educational purposes and when speed matters more than perfect accuracy (e.g., finding prime table sizes). Use Miller-Rabin for any security-critical application like RSA key generation; in practice use a pipeline of small-prime sieve + Fermat (1-2 rounds) + Miller-Rabin (10+ rounds).

Q5: Implement a correct Fermat test in Python and discuss edge cases.

Strong Answer: Write code handling n <2, n=2,3, even n, random base selection in [2, n-2], gcd check, and pow(a, n-1, n) comparison, looping k times. Use pow with three arguments, not **. Discuss edge cases: n=1 (not prime), n=2 (prime), even n (composite), n is Carmichael (false positive), a and n not coprime (should return composite), k=0 (no testing). Mention need for secure randomness in crypto and testing against known values. Provide complexity analysis and note that function should be named is_probable_prime to reflect probabilistic nature.