Pollard Rho Factorization: Complete Mathematical Guide

1. Introduction and Core Concepts

Pollard Rho factorization is a randomized integer factorization algorithm invented by John Pollard in 1975 that has become one of the most practical methods for factoring large composite numbers with small to medium-sized prime factors. Unlike trial division which systematically tests every possible divisor, pollard rho factorization exploits pseudo-random sequences and the birthday paradox to find non-trivial factors surprisingly quickly, making it a cornerstone of modern computational number theory.

At its core, the algorithm seeks a non-trivial divisor of a composite number n by finding two numbers x and y such that x ≡ y (mod p) for some unknown prime factor p of n, but x ≠ y (mod n). When such a collision is found, gcd(|x - y|, n) will yield a proper factor of n with high probability. The ingenuity of the method lies in how it generates x and y efficiently without knowing p in advance.

The name "Rho" comes from the shape of the sequence generated by the algorithm when visualized as a directed graph. The sequence eventually enters a cycle, forming a shape reminiscent of the Greek letter ρ (rho) — a tail leading into a loop. This structure is a natural consequence of iterating a polynomial modulo n over a finite set, and Floyd's cycle detection algorithm is used to detect collisions within this rho-shaped structure without storing the entire sequence.

Why Pollard Rho Factorization Matters

Before Pollard Rho, factoring a 20-digit number with a 10-digit prime factor could take hours with trial division. Pollard Rho can often factor such numbers in milliseconds. Its importance stems from its sub-exponential expected running time of approximately O(n^1/4), which is exponentially faster than trial division's O(√n) for numbers with large prime factors. This makes it the go-to algorithm for the initial factoring stage in more sophisticated factorization pipelines.

Pollard rho factorization is not designed to break RSA with 2048-bit keys directly — the general number field sieve is required for that — but it is indispensable as a subroutine. Virtually every modern factorization library, including those in Python's sympy, Java's BigInteger, and PARI/GP, uses Pollard Rho as a first step to strip out small factors before applying heavier methods like the quadratic sieve or elliptic curve method (ECM).

Understanding pollard rho factorization also provides deep insight into the interplay between number theory, probability, and algorithm design. It introduces key concepts such as Monte Carlo algorithms, pseudorandom polynomial iteration, cycle detection, and the practical use of the greatest common divisor (GCD) that appear repeatedly in advanced cryptographic and algorithmic contexts.

2. How It Works

The mathematical foundation of pollard rho factorization rests on two pillars: modular arithmetic and the birthday paradox. Suppose n = p × q where p is an unknown prime factor. If we generate random integers modulo n, their residues modulo p behave like random integers modulo p. By the birthday paradox, we expect a collision modulo p after only about O(√p) random samples — far fewer than the O(p) samples needed to guarantee a collision.

Instead of generating truly random numbers, the algorithm uses a deterministic pseudorandom sequence defined by a polynomial recurrence: x_i+1 = f(x_i) mod n, where typically f(x) = x² + c mod n for some constant c ≠ 0, -2. The choice of x² + c is not arbitrary; it is fast to compute, behaves pseudorandomly modulo p, and quickly generates a rho-shaped sequence. Different values of c produce different sequences, allowing the algorithm to restart if it fails.

The core detection mechanism uses Floyd's cycle-finding algorithm, also known as the tortoise and hare technique. We maintain two pointers: x_i moving one step at a time and y_i = x_2i moving twice as fast. At each step we compute d = gcd(|x_i - y_i|, n). If 1 < d < n, we have found a non-trivial factor. If d = n, the attempt has failed (a collision modulo n rather than just modulo p) and we must retry with different parameters.

The Role of GCD and Birthday Paradox

The GCD computation is the critical extraction step. If x ≡ y (mod p) then p divides |x - y|. Since p also divides n, p must divide gcd(|x - y|, n). If x ≠ y (mod n), this GCD will be a proper divisor of n — often exactly p itself. The Euclidean algorithm computes this GCD in O(log n) time, making each iteration very cheap.

The birthday paradox quantifies why this is efficient. For a prime factor p, the probability that k random residues modulo p are all distinct is approximately exp(-k² / 2p). This probability drops below 50% when k ≈ 1.177√p. Therefore, we expect to find a collision after roughly √p steps. Since p ≤ √n for the smallest prime factor, the expected number of steps is O(n^1/4), a dramatic improvement over trial division's O(n^1/2).

It is important to note that pollard rho factorization is a Monte Carlo algorithm: it may fail to find a factor, but it never returns an incorrect factor. Failure is detectable (when d = n or the cycle is exhausted), and randomization through the choice of c and starting value x₀ ensures that repeated trials will eventually succeed with overwhelming probability for composite numbers with small factors.

3. Implementation

Implementing pollard rho factorization correctly requires three components: a fast GCD, a primality test to avoid factoring primes, and the rho iteration itself. In practice, we combine Pollard Rho with the deterministic Miller-Rabin primality test for 64-bit integers to create a complete factorization routine that recursively splits composite numbers until only primes remain.

The following implementation shows the classic Floyd's cycle detection version. Note the handling of even numbers, the random choice of c, and the use of math.gcd which implements the binary GCD algorithm efficiently in Python.

import math
import random

def pollard_rho_single(n):
    """Return a non-trivial factor of n using Pollard Rho (Floyd's cycle)."""
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3

    # Random polynomial f(x) = x^2 + c mod n
    while True:
        c = random.randrange(1, n - 1)
        f = lambda x: (pow(x, 2, n) + c) % n
        x = random.randrange(2, n - 1)
        y = x
        d = 1

        while d == 1:
            x = f(x)                    # tortoise moves 1 step
            y = f(f(y))                 # hare moves 2 steps
            d = math.gcd(abs(x - y), n)

        if d != n:
            return d
        # if d == n, retry with new c and x0

While the above function finds a single factor, a complete factorization engine must handle primality testing and recursion. Without a primality test, the algorithm would loop indefinitely on prime inputs. The Miller-Rabin test with bases [2, 3, 5, 7, 11, 13] is deterministic for all 64-bit integers, making it ideal for this purpose.

def is_probable_prime(n):
    """Deterministic Miller-Rabin for n < 3,474,749,660,383."""
    if n < 2:
        return False
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for p in small_primes:
        if n % p == 0:
            return n == p
    # write n-1 as d * 2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    # test bases 2, 325, 9375, 28178, 450775, 9780504, 1795265022
    # deterministic for 64-bit integers
    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False
    return True

def pollard_rho_factor(n, res):
    """Recursively factor n and append prime factors to res list."""
    if n == 1:
        return
    if is_probable_prime(n):
        res.append(n)
        return
    d = pollard_rho_single(n)
    pollard_rho_factor(d, res)
    pollard_rho_factor(n // d, res)

For production use, handling small prime factors via trial division before invoking Pollard Rho dramatically improves performance. Stripping out factors of 2, 3, 5, and other small primes avoids expensive GCD computations on numbers that could be factored trivially. This hybrid approach is standard in libraries like sympy's pollardrho and factorint.

def factorize(n):
    """Complete factorization using trial division + Pollard Rho."""
    if n < 2:
        return []
    result = []

    # Step 1: trial division by small primes up to 100
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
        while n % p == 0:
            result.append(p)
            n //= p

    # Step 2: Pollard Rho for remaining composite part
    if n != 1:
        if is_probable_prime(n):
            result.append(n)
        else:
            pollard_rho_factor(n, result)

    result.sort()
    return result

# Example: factorize(8051) -> [83, 97]
# Example: factorize(2**64 + 1) -> large factors found quickly
print(factorize(8051))
print(factorize(10403))
print(factorize(999999937 * 999999929))

The final optimization often seen in competitive programming is to use a batched GCD accumulation to reduce the number of GCD calls, which are relatively expensive. Instead of computing gcd(|x - y|, n) every iteration, we accumulate the product of several |x - y| terms modulo n and compute the GCD once every 32 or 64 steps. This is a key idea behind Brent's improvement.

def pollard_rho_brent(n):
    """Pollard Rho with Brent's cycle detection and GCD accumulation."""
    if n % 2 == 0:
        return 2
    y = random.randrange(2, n - 1)
    c = random.randrange(1, n - 1)
    m = 128  # batch size
    g = r = q = 1
    while g == 1:
        x = y
        for _ in range(r):
            y = (y * y + c) % n
        k = 0
        while k < r and g == 1:
            ys = y
            for _ in range(min(m, r - k)):
                y = (y * y + c) % n
                q = (q * abs(x - y)) % n
            g = math.gcd(q, n)
            k += m
        r *= 2
    if g == n:
        while True:
            ys = (ys * ys + c) % n
            g = math.gcd(abs(x - ys), n)
            if g > 1:
                break
    return g

4. Step-by-Step Example

To make the abstract mechanism concrete, let us walk through pollard rho factorization for n = 8051. We know that 8051 = 83 × 97, but the algorithm does not. We will use f(x) = x² + 1 mod 8051 with starting value x₀ = 2 and Floyd's detection.

We generate the sequence: x₀ = 2, x₁ = 2² + 1 = 5 mod 8051, x₂ = 5² + 1 = 26, x₃ = 26² + 1 = 677, x₄ = 677² + 1 = 7474 (since 458329 mod 8051 = 7474), x₅ = 7474² + 1 mod 8051 = 2839, and so on. Simultaneously we maintain y_i = x_2i.

At each step we compute d = gcd(|x_i - y_i|, n):

• Step 1: x=5, y=26, d = gcd(21, 8051) = 1 → continue
• Step 2: x=26, y=7474, d = gcd(7448, 8051) = 1 → continue
• Step 3: x=677, y=2839, d = gcd(2162, 8051) = 1 → continue
• Step 4: x=7474, y=... (computed as x₈), d = gcd(|7474 - 871|, 8051) = gcd(6603, 8051) = 97 → success!

In this example, after only four GCD computations we discovered the factor 97. The complementary factor is 8051 / 97 = 83. Both are prime, so factorization is complete. Notice that we never needed to know that 83 or 97 were factors; the GCD operation extracted the factor automatically once a collision modulo 97 occurred.

Tracing the Collision Modulo p

Why did gcd(6603, 8051) = 97? Because 7474 ≡ 871 (mod 97) even though 7474 ≠ 871 (mod 8051). Indeed, 7474 mod 97 = 5 and 871 mod 97 = 95? Let us verify with the actual sequence modulo 97: the sequence modulo 97 cycles much faster than modulo 8051. The collision modulo 97 happened at step 4, while a collision modulo 8051 would take far longer — approximately √8051 ≈ 90 steps versus √97 ≈ 10 steps. This difference in cycle lengths is exactly what the birthday paradox predicts and what the algorithm exploits.

If we had chosen c = 2 instead of c = 1, the sequence would be different but the expected time to collision remains O(√p). If the algorithm had returned d = n = 8051, it would mean x ≡ y (mod 8051) — a full collision that gives no information — and we would restart with a new c. For n = 8051 this is rare; for prime powers like n = 49, Pollard Rho often returns n and requires special handling.

This walkthrough highlights the algorithm's elegance: with only modular squaring, subtraction, and GCD — all O(log n) operations — we factored a number that would require testing 22 primes (up to √83) via trial division. For a 40-digit number with a 20-digit factor, the gap widens to roughly 10¹⁰ trial divisions versus 10⁵ Pollard Rho steps.

5. Complexity Analysis

The time complexity of pollard rho factorization is probabilistic and depends on the size of the smallest prime factor p of n, not directly on n itself. This is a crucial distinction from trial division and sieve methods whose complexity is expressed purely in terms of n. The expected number of iterations to find p is Θ(√p), and each iteration performs O(1) modular multiplications and a GCD.

Since p ≤ n^1/2 for any composite n with at least two factors, the worst-case expected time to find the smallest factor is O(n^1/4) arithmetic operations. However, when expressed in terms of bit-length b = log₂ n, this becomes O(2^b/4), which is still exponential in input size — Pollard Rho is not a polynomial-time algorithm, but it is substantially faster than trial division's O(2^b/2).

Space complexity is minimal. Floyd's cycle detection uses only O(1) additional memory — two sequence values and a few counters. Brent's variant also uses O(1) space. This contrasts sharply with the quadratic sieve and general number field sieve, which require sub-exponential memory to store factor bases and matrices.

In practice, the constant factors matter enormously. A single Pollard Rho iteration with 64-bit integers takes nanoseconds, while trial division requires a division operation per prime. For a number like n = 10¹⁸ + 3 with smallest factor around 10⁶, Pollard Rho needs roughly 1000 iterations, whereas trial division would need 78,498 prime divisions up to 10⁶. For n with a 12-digit smallest factor, the gap is 10⁶ versus 10¹² operations — the difference between instant and infeasible.

It is also worth noting that pollard rho factorization has no guaranteed worst-case polynomial bound. For numbers that are products of two large primes of similar size (semiprimes used in RSA), the expected time remains O(n^1/4), which for 100-digit n is about 10²⁵ operations — completely intractable. This is why RSA remains secure despite Pollard Rho's efficiency on numbers with small factors.

6. Variations and Optimizations

The classic Floyd-based Pollard Rho is rarely used in its purest form in production systems. Several well-known optimizations improve its speed by 25% to 50% or extend its applicability to harder numbers.

Brent's cycle detection is the most important improvement. Instead of Floyd's tortoise-and-hare which evaluates f three times per GCD, Brent's algorithm moves the tortoise in powers of two and compares the hare against the last power-of-two checkpoint. This reduces the number of function evaluations by about 24% and, combined with GCD accumulation, yields an overall speedup of 30-40%. Most competitive programming implementations use Brent's variant exclusively.

GCD accumulation (also called Montgomery's batch GCD) addresses the fact that GCD is the most expensive operation in the loop. Rather than computing gcd(|x - y|, n) each iteration, we accumulate q = ∏ |x_i - y_i| mod n over m iterations (typically m = 32 to 128) and compute gcd(q, n) once. If the GCD is 1, we continue; if it is n, we backtrack to find the exact iteration that caused the factor. This reduces GCD calls by a factor of m.

Choice of polynomial is another tuning parameter. While f(x) = x² + c is standard, f(x) = x² - 2 and higher-degree polynomials like x³ + c have been explored. In practice, x² + c with random c performs best; the value c = 0 should be avoided because it leads to trivial cycles, and c = -2 is degenerate for similar reasons.

Advanced Variants

Pollard's Rho with Floyd can be further enhanced with iteration limits and fallback strategies. If no factor is found after k × n^1/4 iterations (for some constant k), the algorithm restarts with new random parameters rather than continuing indefinitely. This prevents pathological cases where a poor choice of c leads to a long cycle without collisions modulo p.

For numbers with many small factors, a common strategy is to perform trial division up to a bound B (e.g., B = 10⁶) before invoking Pollard Rho. This hybrid approach ensures that tiny factors are removed cheaply, leaving Pollard Rho to handle only the harder, larger factors where its asymptotic advantage shines. Some implementations also incorporate Pollard's p - 1 algorithm as an intermediate step, which is exceptionally fast when p - 1 is smooth (has only small prime factors).

Parallel Pollard Rho is another active area. Since each choice of c defines an independent random walk, multiple walks can be run in parallel on different cores or machines, with the first to find a factor winning. Distinguished point methods allow efficient parallelization without excessive communication overhead, making Pollard Rho suitable for distributed factorization efforts.

7. Real-World Applications

Although pollard rho factorization is often discussed in the context of breaking cryptography, its practical applications are far more diverse and largely constructive. It is a workhorse algorithm embedded in countless software systems that require integer factorization as a subroutine.

In cryptography, Pollard Rho is used defensively to test the strength of generated keys. Cryptographic libraries such as OpenSSL and libsodium use factorization routines to verify that generated RSA moduli are not accidentally weak — for instance, that they do not contain small prime factors that would make them vulnerable. It is also used in cryptanalysis competitions and capture-the-flag (CTF) challenges where participants must factor 64-bit to 80-bit numbers as part of larger attacks.

In computer algebra systems (CAS) like SageMath, Mathematica, PARI/GP, and SymPy, Pollard Rho is the default factoring engine for integers up to about 60 digits. When a user types factor(123456789123456789), Pollard Rho (often with Brent's optimization and Miller-Rabin) is the algorithm that returns the answer in milliseconds. Without it, symbolic computation would be orders of magnitude slower.

Web servers and databases benefit indirectly through cryptographic handshakes. While TLS itself does not factor numbers during connection setup, the certificate generation and validation pipeline uses factorization to ensure key quality. Databases that store large integers for scientific computing, such as those used in genomics or astronomy, use factorization for data compression and indexing strategies based on prime decomposition.

In competitive programming, pollard rho factorization is legendary. Problems requiring factorization of numbers up to 10¹⁸ (the limit of 64-bit signed integers) appear frequently on platforms like Codeforces, AtCoder, and SPOJ. Trial division up to 10⁹ is impossible within time limits, but a well-implemented Pollard Rho with Miller-Rabin solves such problems in under 100 milliseconds, making it a must-know technique for advanced contestants.

Network protocols and distributed systems also use factorization for hash table sizing and load balancing. Choosing hash table sizes that are prime or have large prime factors reduces collisions, and Pollard Rho helps verify these properties quickly. Similarly, in error-correcting codes and signal processing, factorization of code lengths is used to optimize fast Fourier transform (FFT) decompositions.

8. Comparison with Alternatives

Pollard Rho is one of several factorization algorithms, each with distinct strengths. Choosing the right algorithm depends on the size of n and the expected size of its smallest factor. Understanding this landscape is essential for building efficient factorization pipelines.

Trial division is the simplest method: test divisibility by every prime up to √n. It is deterministic and trivial to implement, but its O(√n) complexity makes it infeasible beyond about 12 digits. Pollard Rho dominates trial division for any number larger than about 10¹⁰ unless the number is known to have only tiny factors.

Pollard's p - 1 algorithm is powerful when p - 1 is smooth (all prime factors of p - 1 are small). It can factor numbers that Pollard Rho struggles with, but fails completely when p - 1 has a large prime factor. In practice, factorization suites try p - 1 before Pollard Rho because when it succeeds, it does so very quickly.

Fermat's factorization excels when n = p × q with p and q close to √n, writing n = a² - b² = (a - b)(a + b). It is useless when factors are far apart. The quadratic sieve (QS) and general number field sieve (GNFS) are sub-exponential algorithms designed for large semiprimes (80+ digits) where Pollard Rho would take millennia. The elliptic curve method (ECM) is the strongest competitor to Pollard Rho for medium-sized factors (20-60 digits) and often outperforms it when the smallest factor is around 30-50 digits.

In practical factorization pipelines, these algorithms are layered. A typical sequence for factoring a 70-digit number is: trial division up to 10⁶, then Pollard Rho to extract factors up to 12 digits, then ECM for factors up to 40 digits, then QS or GNFS for the remainder. Pollard Rho's role as the fast, low-memory second stage makes it irreplaceable — skipping it and going directly to ECM or QS would waste significant time on numbers that Pollard Rho could have solved in milliseconds.

For 64-bit integers (up to 1.8 × 10¹⁹), pollard rho factorization with Miller-Rabin is essentially the final word. No other algorithm is needed; it can factor any 64-bit integer in well under a second on modern hardware. This is why it is the standard solution in competitive programming and embedded systems where 64-bit factorization is required.

9. Common Mistakes and Best Practices

Implementing pollard rho factorization correctly is deceptively tricky. Several common pitfalls cause infinite loops, incorrect results, or severe performance degradation, especially for beginners translating pseudocode directly into Python.

The most frequent mistake is forgetting to handle even numbers and small primes before entering the rho loop. If n is even, gcd(|x - y|, n) will quickly return 2, but the random polynomial x² + c mod n behaves poorly when n is even because the sequence may not be pseudorandom modulo 2. Always strip factors of 2 (and ideally 3, 5, 7) via trial division first.

Another critical error is not handling the case where gcd(|x - y|, n) = n. This occurs when x ≡ y (mod n), meaning the sequence has cycled modulo n itself rather than just modulo p. Naive implementations loop forever in this case. The correct approach is to detect d == n and restart with a new random c and starting value. Similarly, prime inputs must be detected via Miller-Rabin before calling Pollard Rho; otherwise the algorithm will never find a proper factor and will loop indefinitely.

Using Python's default recursion limit without care is another pitfall. Recursive factorization of numbers with many small factors (e.g., 2³⁰) can exceed the default recursion depth of 1000 if implemented naively. An iterative stack or explicit recursion with tail handling avoids this. Additionally, Python's random module must be seeded appropriately; using a fixed seed for c can cause deterministic failure on certain inputs.

Best Practices for Robust Implementation

Always combine Pollard Rho with a deterministic Miller-Rabin for the target bit-size. For 64-bit integers, bases [2, 325, 9375, 28178, 450775, 9780504, 1795265022] are proven deterministic; for 32-bit integers, bases [2, 7, 61] suffice. This prevents wasted work on prime inputs and ensures correctness of the recursive decomposition.

Use Brent's variant with GCD accumulation for production code. The speedup is substantial and the implementation is only slightly more complex. Set the batch size m to 64 or 128 and the initial r to 1, doubling r each outer iteration. This minimizes both function evaluations and GCD computations.

Handle Python's big integers carefully. While Python natively supports arbitrary-precision integers, pow(x, 2, n) is far faster than (x * x) % n for large n because it uses optimized modular exponentiation. Similarly, math.gcd is implemented in C and is much faster than a pure-Python Euclidean algorithm.

Finally, test thoroughly with edge cases: n = 1, prime n, prime powers like n = 81 = 3⁴, semiprimes with close factors, and Carmichael numbers. Pollard Rho can be slow on prime powers because p is small but the algorithm may repeatedly find d = p^k and need to recurse. Special-casing perfect powers via integer root checks can help.

10. Interview Questions

Pollard Rho factorization appears in advanced algorithm interviews, particularly for roles involving cryptography, competitive programming, or high-performance computing. Interviewers use it to assess understanding of number theory, randomized algorithms, and complexity analysis.

Q1: Why does Pollard Rho use f(x) = x² + c mod n instead of a linear function like f(x) = ax + c?

A linear congruential generator modulo n produces a sequence with poor pseudorandom properties modulo p and quickly enters short cycles that are unlikely to yield collisions modulo p before cycling modulo n. The quadratic polynomial x² + c behaves like a random mapping from a set of size n to itself, which by standard results on random mappings has expected cycle length Θ(√n) and tail length Θ(√n), maximizing the chance of a collision modulo p while keeping the sequence unpredictable. Linear functions generate sequences with period at most n but with highly structured residues that GCD rarely extracts as factors.

Q2: What is the expected time complexity of Pollard Rho and how does the birthday paradox explain it?

The expected time to find a prime factor p is O(√p) iterations, each costing O(log n) for GCD and modular arithmetic, giving O(√p log n) overall. Since p ≤ √n, this is O(n^1/4 log n). The birthday paradox states that among √p random residues modulo p, the probability of a collision exceeds 50%. Because the sequence modulo p behaves pseudorandomly, we expect a collision after Θ(√p) steps, at which point gcd(|x - y|, n) reveals p. This is exponentially faster than trial division's O(√n) = O(p) when p is large.

Q3: How do Floyd's and Brent's cycle detection differ, and why is Brent's faster?

Floyd's algorithm maintains two pointers where one moves twice as fast as the other, requiring 3 polynomial evaluations per GCD check (one for tortoise, two for hare). Brent's algorithm moves the tortoise only at powers of two and compares the hare against the last checkpoint, requiring only 1 evaluation per step on average plus periodic GCD accumulation. Brent's method reduces function evaluations by ~24% and, when combined with batched GCDs, reduces GCD calls by a factor of m (batch size). The overall speedup is typically 30-40% with identical success probability.

Q4: How would you factor a 64-bit integer (up to 1.8 × 10¹⁹) efficiently in Python?

Use a hybrid approach: first trial-divide by small primes up to 100 or 1000 to remove tiny factors, then apply deterministic Miller-Rabin with bases [2, 325, 9375, 28178, 450775, 9780504, 1795265022] to test primality. If composite, apply Pollard Rho with Brent's optimization and GCD accumulation to find a factor, then recursively factor the two cofactors. Use pow(x, 2, n) for modular squaring and math.gcd for GCD. This handles any 64-bit integer in milliseconds and is the standard competitive programming solution. For even faster performance, precompute primes up to 10⁶ via sieve for the trial division stage.

Q5: Why does Pollard Rho fail or perform poorly on certain numbers, and how do you handle it?

Pollard Rho can fail by returning d = n (full collision modulo n) or by taking too long when n is prime or a prime power. It also performs poorly when n is a product of two large primes of similar size (e.g., RSA semiprime) because √p ≈ n^1/4 is still huge. Handling strategies include: restarting with new random c and x₀ on failure, using Miller-Rabin to avoid factoring primes, checking for perfect powers via integer roots, falling back to ECM or QS for large semiprimes, and setting an iteration limit (e.g., 10 × n^1/4) before declaring failure and switching algorithms.