Primality Testing & Integer Factorization

Intuition, Vocabulary and Foundations

Primality testing asks whether an integer has any nontrivial divisors; factorization asks what those divisors are. A test can often prove compositeness without revealing even one factor.

Think of a primality test as an identity check. A prime satisfies strong arithmetic rules, so a candidate is challenged with selected inputs called bases. If one challenge contradicts prime behavior, the base is a witness proving compositeness. Passing only means that this base failed to expose the number.

Fermat's little theorem states that if $p$ is prime and $p\nmid a$, then

$$ a^{p-1}\equiv1\pmod p. $$

Therefore, $a^{n-1}\not\equiv1\pmod n$ proves that $n$ is composite. The converse is false. A composite passing this test is a Fermat pseudoprime to base $a$. For example,

$$ 2^{340}\equiv1\pmod{341}, \qquad341=11\cdot31. $$

A Carmichael number is composite but passes the Fermat test for every base coprime to it. The smallest is $561=3\cdot11\cdot17$.

Miller–Rabin strengthens the test by examining square roots of $1$. For odd $n\gt2$, write $n-1=d2^s$ with $d$ odd. If $n$ is prime, then either $a^d\equiv1\pmod n$ or some member of the squaring chain satisfies $a^{d2^r}\equiv-1\pmod n$ for $0\le r\lt s$. A base violating both conditions is a strong witness.

For any odd composite, at most one quarter of possible bases are strong liars, so $k$ independent random rounds have false-prime probability at most $4^{-k}$. For unsigned $64$-bit integers, a proven fixed base set makes the test deterministic.

Factorization is generally harder. Trial division needs up to $O(\sqrt n)$ candidates. Pollard rho instead generates a pseudorandom modular sequence and searches for a collision modulo an unknown factor; a gcd converts that hidden collision into a divisor.

A failed primality round proves compositeness, but a passed probabilistic round is only evidence. Deterministic claims require a base set proven for the exact input range, while factorization additionally requires retries because a rho walk may return only $1$ or the original number.

Concept	Concrete example	Non-example or limitation	Required assumption	Question answered
Composite witness	A base exposes a failed prime identity	A passing base need not prove primality	Correct modular exponentiation	Can this base prove compositeness?
Fermat pseudoprime	$341$ passes base $2$	$341=11\cdot31$ is composite	Base coprime to the candidate	Why is one Fermat round insufficient?
Carmichael number	$561=3\cdot11\cdot17$ passes every coprime Fermat base	Passing all such Fermat tests still does not prove primality	Composite satisfying Korselt's criterion	Why can Fermat testing fail systematically?
Strong witness	Its Miller–Rabin chain reaches neither valid endpoint	A strong liar remains possible for a composite	Odd candidate greater than $2$	Does square-root structure expose compositeness?
Random Miller–Rabin	$k$ independent bases give error at most $4^{-k}$	Predictable adversarial bases may violate the model	Appropriate independent sampling	How much confidence do random rounds provide?
Deterministic 64-bit test	Seven proven bases decide every $n\lt2^{64}$	The guarantee does not extend beyond the bound	Exact unsigned $64$-bit domain	Can machine integers be decided without error?
Pollard rho factor	A walk may reveal $83$ from $8051=83\cdot97$	An unlucky walk may return $8051$	Composite input and retries	Can a factor be found without scanning to $\sqrt n$?
Factorization complexity	Rho heuristically costs about $O(\sqrt p)$ for factor $p$	This is not a worst-case polynomial guarantee	Pseudorandom-walk heuristic	What practical cost should be expected?

Step-by-Step Derivations and Algorithms

Begin by rejecting $n\lt2$, accepting small primes, and removing divisibility by a short list of small primes. These checks handle even values and reduce expensive modular exponentiation.

A Fermat round computes $a^{n-1}\bmod n$ with binary exponentiation. A value other than $1$ proves compositeness; a value of $1$ is inconclusive because pseudoprimes exist.

Miller–Rabin factors $n-1=d2^s$, computes $x_0=a^d\bmod n$, and accepts the base if $x_0=1$ or $x_0=n-1$. Otherwise it repeatedly squares. Encountering $n-1$ passes the base; encountering $1$ first exposes a nontrivial square root of $1$; exhausting the chain also proves compositeness.

For every unsigned integer below $2^{64}$, the bases

$$ 2, 325, 9375, 28178, 450775, 9780504, 1795265022 $$

form a deterministic test. This theorem must not be extrapolated to larger integers.

Pollard rho chooses a polynomial such as $f(x)=x^2+c\pmod n$ and generates $x_{i+1}=f(x_i)$. If $n=pq$, a collision modulo $p$ makes $p\mid(x_i-x_j)$, so $\gcd(\lvert x_i-x_j\rvert,n)$ may reveal $p$.

Floyd detection compares walkers moving at different speeds. Brent detection expands intervals geometrically and batches differences into a product before taking a gcd, usually reducing costly gcd calls.

A complete pipeline removes tiny factors, primality-tests every remaining value, splits composites with Pollard–Brent, recursively processes both factors, and retries with new parameters after a degenerate walk.

Primality Testing & Integer Factorization algorithm map

flowchart TD
    A["Validate input and remove small factors"] --> B{"Remainder equals one?"}
    B -->|Yes| C["Return collected factors"]
    B -->|No| D{"Deterministic Miller-Rabin says prime?"}
    D -->|Yes| E["Record prime factor"]
    D -->|No| F["Start Pollard-Brent walk"]
    F --> G{"Nontrivial divisor found?"}
    G -->|No| H["Choose new seed and polynomial"]
    H --> F
    G -->|Yes| I["Split divisor and cofactor"]
    I --> D
    E --> B

Miller–Rabin is correct because a prime's squaring chain must begin at $1$ or encounter $-1$ before reaching $1$; violating that structure proves compositeness. Each base uses $O(\log n)$ modular multiplications, while Pollard rho heuristically finds a factor $p$ in $O(\sqrt p)$ modular steps with $O(1)$ walk storage.

Implementation, Complexity and Engineering

For fixed-width languages, modular multiplication is the first correctness boundary: $ab$ may overflow before reduction. Use a wider intermediate type or a proven technique such as double-and-add, Barrett reduction, or Montgomery multiplication.

The deterministic bases below are valid only for $0\le n\lt2^{64}$. Pollard rho is Las Vegas: every returned divisor is verified exactly, but runtime varies. Production code needs randomized retries, small-prime preprocessing, and adversarial tests involving prime powers, Carmichael numbers, strong pseudoprimes, balanced semiprimes, and boundary values.

from collections import Counter
from math import gcd
from random import Random


UINT64_LIMIT = 1 << 64
MR_BASES_64 = (2, 325, 9375, 28178, 450775, 9780504, 1795265022)
SMALL_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)


def multiply_mod(a: int, b: int, modulus: int) -> int:
    if modulus <= 0:
        raise ValueError("modulus must be positive")
    a %= modulus
    b %= modulus
    result = 0
    while b:
        if b & 1:
            result = (result + a) % modulus
        a = (a + a) % modulus
        b >>= 1
    return result


def power_mod(base: int, exponent: int, modulus: int) -> int:
    if modulus <= 0 or exponent < 0:
        raise ValueError("invalid exponent or modulus")
    base %= modulus
    result = 1 % modulus
    while exponent:
        if exponent & 1:
            result = multiply_mod(result, base, modulus)
        base = multiply_mod(base, base, modulus)
        exponent >>= 1
    return result


def is_prime_64(value: int) -> bool:
    if not 0 <= value < UINT64_LIMIT:
        raise ValueError("value must be an unsigned 64-bit integer")
    if value < 2:
        return False
    for prime in SMALL_PRIMES:
        if value == prime:
            return True
        if value % prime == 0:
            return False

    odd_part = value - 1
    twos = 0
    while odd_part % 2 == 0:
        odd_part //= 2
        twos += 1

    for base in MR_BASES_64:
        base %= value
        if base == 0:
            continue
        x = power_mod(base, odd_part, value)
        if x == 1 or x == value - 1:
            continue
        for _ in range(twos - 1):
            x = multiply_mod(x, x, value)
            if x == value - 1:
                break
            if x == 1:
                return False
        else:
            return False
    return True


def pollard_brent(value: int, rng: Random) -> int:
    if value % 2 == 0:
        return 2
    if value % 3 == 0:
        return 3
    if value < 2 or is_prime_64(value):
        raise ValueError("Pollard-Brent requires a composite input")

    while True:
        y = rng.randrange(1, value)
        c = rng.randrange(1, value)
        batch_size = rng.randrange(1, min(value, 128) + 1)
        cycle_length = 1
        divisor = 1
        saved_y = y

        while divisor == 1:
            x = y
            for _ in range(cycle_length):
                y = (multiply_mod(y, y, value) + c) % value

            offset = 0
            while offset < cycle_length and divisor == 1:
                saved_y = y
                product = 1
                steps = min(batch_size, cycle_length - offset)
                for _ in range(steps):
                    y = (multiply_mod(y, y, value) + c) % value
                    product = multiply_mod(product, abs(x - y), value)
                divisor = gcd(product, value)
                offset += steps
            cycle_length *= 2

        if divisor == value:
            while True:
                saved_y = (multiply_mod(saved_y, saved_y, value) + c) % value
                divisor = gcd(abs(x - saved_y), value)
                if divisor > 1:
                    break

        if divisor != value:
            return divisor


def factor_integer(value: int, seed: int = 0) -> dict[int, int]:
    if value == 0:
        raise ValueError("zero has no finite prime factorization")
    value = abs(value)
    if value >= UINT64_LIMIT:
        raise ValueError("absolute value must be below 2**64")
    if value == 1:
        return {}

    factors: list[int] = []
    for prime in SMALL_PRIMES:
        while value % prime == 0:
            factors.append(prime)
            value //= prime

    rng = Random(seed)
    pending = [value] if value > 1 else []
    while pending:
        current = pending.pop()
        if current == 1:
            continue
        if is_prime_64(current):
            factors.append(current)
            continue
        divisor = pollard_brent(current, rng)
        pending.append(divisor)
        pending.append(current // divisor)

    return dict(sorted(Counter(factors).items()))


assert not is_prime_64(0)
assert not is_prime_64(1)
assert is_prime_64(2)
assert is_prime_64(97)
assert not is_prime_64(341)
assert not is_prime_64(561)
assert not is_prime_64(3_215_031_751)
assert not is_prime_64(341_550_071_728_321)
assert is_prime_64(18_446_744_073_709_551_557)

assert factor_integer(1) == {}
assert factor_integer(-84) == {2: 2, 3: 1, 7: 1}
assert factor_integer(561) == {3: 1, 11: 1, 17: 1}
assert factor_integer(8051) == {83: 1, 97: 1}
assert factor_integer(600_851_475_143) == {
    71: 1,
    839: 1,
    1471: 1,
    6857: 1,
}

for operation in (
    lambda: is_prime_64(-1),
    lambda: is_prime_64(UINT64_LIMIT),
    lambda: factor_integer(0),
    lambda: factor_integer(UINT64_LIMIT),
):
    try:
        operation()
        raise AssertionError("expected ValueError")
    except ValueError:
        pass

print("all primality and factorization tests passed")

Method	Expected or worst-case cost	Numeric boundary	Failure mode	Engineering mitigation
Trial division	$O(\sqrt n)$ divisions worst case	Useful for small factors	Scanning to $\sqrt n$ for a large prime	Remove small factors, then switch methods
Fermat test	$O(\log n)$ modular multiplications per base	One-sided compositeness test only	Pseudoprimes and Carmichael numbers pass	Use Miller–Rabin for decisions
Random Miller–Rabin	$O(k\log n)$ modular multiplications	Error depends on base selection	Calling a probable prime definitely prime	State the error policy and sample correctly
Deterministic 64-bit Miller–Rabin	Seven rounds after preprocessing	Proven only below $2^{64}$	Reusing the bases for larger integers	Enforce the domain
Floyd Pollard rho	Heuristic $O(\sqrt p)$ for factor $p$	Constant walk storage	Excessive gcd calls or bad cycles	Retry and prefer Brent batching
Pollard–Brent	Heuristic $O(\sqrt p)$ modular steps	Products require safe reduction	A batch gcd equals the input	Replay steps and restart if necessary
Recursive factor pipeline	Depends on discovered factors	Repeated factors and depth matter	Recording a composite leaf	Primality-test every leaf and reconstruct
Native modular product	Usually constant machine time	$ab$ may overflow	Silent corruption of all later decisions	Use a wider type or safe multiplication

Applications, Case Studies and Exercises

A robust machine-integer pipeline combines methods. Small-prime division removes common factors, deterministic Miller–Rabin classifies remaining $64$-bit values, and Pollard–Brent splits composites. Every reported factor should be retested, sorted, counted, and multiplied back to reconstruct the original absolute value.

Testing whether an integer is prime does not demonstrate that it was generated unpredictably. Factoring arbitrary cryptographic-size semiprimes also remains outside this pipeline's scope: these methods target machine integers and algorithmic workloads, not key recovery.

Practice

Apply Primality Testing & Integer Factorization

Case study 1 — expose a weak primality test. Investigate $561$.

Confirm $561=3\cdot11\cdot17$.
Compute $2^{560}\bmod561$ and observe the Fermat result $1$.
Decompose $560=35\cdot2^4$.
Run the Miller–Rabin chain from $2^{35}\bmod561$.
Identify where the chain violates prime behavior.

Success criterion: explain why Fermat misclassifies $561$ while Miller–Rabin supplies a witness.

Case study 2 — factor a machine-sized value. Factor $600851475143$.

Remove small factors.
Apply deterministic Miller–Rabin to every remaining candidate.
Use Pollard–Brent whenever a candidate is composite.
Continue until every leaf is prime.
Verify

$$ 600851475143=71\cdot839\cdot1471\cdot6857. $$

Success criterion: every factor passes the deterministic test and their product reconstructs the input.

Adversarial validation set: include $0$, $1$, $2$, negative inputs, prime powers, Carmichael numbers, strong pseudoprimes, balanced semiprimes, $2^{64}-59$, and values outside the declared range.

Tiered exercises

Recall: Distinguish a witness, liar, pseudoprime, and Carmichael number.
Trace: Perform one Miller–Rabin round for $221$ with base $2$.
Derivation: Explain why a nontrivial square root of $1$ proves compositeness.
Implementation: Replace double-and-add with a verified wide product and benchmark it.
Debugging: Find the error in a test that accepts when any base passes.
Testing: Verify factors by retesting them and reconstructing the input.
Probability: Find how many random rounds make the error bound smaller than $2^{-128}$.
Engineering: Add retry and iteration metrics to Pollard–Brent.
Extension: Detect perfect powers before starting rho.
Challenge: Compare Floyd and Brent detection across semiprime shapes.

Use trial division for tiny factors, deterministic Miller–Rabin only within its proven $64$-bit range, and Pollard–Brent with verified randomized retries for splitting. Never equate a Fermat pass with primality, extrapolate a base theorem beyond its domain, or trust factors without reconstructing the input; the next step is to study prime-counting sieves and multiplicative functions at scale.

Next in the Series

In Arithmetic Functions, Convolution & Möbius Inversion, we'll explore Exploit multiplicativity and convolution to transform counting problems..

PreviousLinear Congruences & Chinese Remainder Theorem Next Arithmetic Functions, Convolution & Möbius Inversion

Cookie Consent

Primality Testing & Integer Factorization

Table of Contents

Intuition, Vocabulary and Foundations

Step-by-Step Derivations and Algorithms

Implementation, Complexity and Engineering

Applications, Case Studies and Exercises

Apply Primality Testing & Integer Factorization

Next in the Series

Cookie Consent

Primality Testing & Integer Factorization

Table of Contents

Intuition, Vocabulary and Foundations

Step-by-Step Derivations and Algorithms

Implementation, Complexity and Engineering

Applications, Case Studies and Exercises

Apply Primality Testing & Integer Factorization

Next in the Series

Continue the Series

Sieves & Bulk Precomputation

Modular Arithmetic & Fast Exponentiation