Overview
Pollard's rho iterates a simple polynomial modulo n and periodically computes gcd differences between two sequence positions. When the sequence collides modulo a hidden factor, the gcd can reveal a nontrivial divisor.
CoreSource checked
Pollard's Rho Factorization
Finds a nontrivial factor by searching for cycles in a pseudorandom modular sequence.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Cryptography
- Difficulty
- Intermediate
- Family
- Integer Factorization
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
integer factorizationmodular arithmeticfactorizationrandom samplingcryptography
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(k)
Average
O(k^2)
Worst
O(k^3)
Space
O(k)
When to Use
- Use when trial division is too slow but the integer may still have moderate-size factors.
- Use with restarts when the polynomial or seed produces an unhelpful cycle.
When Not to Use
- Avoid treating it as a complete large-integer factorization strategy by itself.
- Avoid if gcd, modular multiplication, or restart handling is not robust for the input size.
What It Does
- Generates a pseudorandom sequence modulo n
- Uses cycle detection to compare sequence positions
- Computes gcd differences to expose a factor
Use Cases
- Factoring composite integers after primality screening
- Finding small or medium factors in number-theory tools
- Demonstrating cycle-finding methods in modular arithmetic
Inputs
- Message, key, modulus, seed, or public parameters
- Security parameter or nonce when required
Outputs
- Cryptographic value such as signature, random bits, proof, or modular result
Pseudocode
- 1.Handle even n and return if n is probably prime
- 2.Choose a seed x and polynomial f modulo n
- 3.Set y = x and d = 1
- 4.While d = 1, advance x once and y twice
- 5.Set d = gcd(abs(x - y), n)
- 6.If d is n, restart with a new seed or polynomial
- 7.Return d as a nontrivial factor
Canonical Example
- Input
- n = 8051 with f(x) = x^2 + 1
- Output
- factor = 97 or 83
- Explanation
- The modular sequence eventually creates a difference divisible by one hidden factor, and gcd reveals that factor.
Implementation Notes
- Handle even numbers and probable primes before starting the rho loop.
- Use Floyd or Brent cycle detection and compute gcd(abs(x - y), n).
- Restart with a different seed or polynomial when the search degenerates.
Common Pitfalls
- Failing to restart when gcd returns n stalls the factor search.
- Overflow in modular squaring can corrupt the sequence.
- Using one fixed polynomial and seed can miss easy factors on unlucky inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow using cycle detection over modular pseudorandom walks on a small integer factorization example.
Step 1 of 7: Handle even n and return if n is probably prime
cryptography-mechanismNotes
Pollard's rho is randomized in practice; restart policy is part of the algorithm's reliability.
Sources (2)
What each reference supports for this entry.
Handbook of Applied Cryptography
BookCryptographic reference for Pollard's Rho Factorization's number-theoretic primitive, modular arithmetic, primality, or factorization context.
Open sourceModern Computer Arithmetic
BookReference for Pollard's Rho Factorization's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageOften paired withMiller-Rabin Primality Test
Primality testing usually checks whether a candidate factor still needs factoring.
Pollard's rho repeatedly uses gcd computations to expose factors.
Related Algorithms
Tags
CryptographyRandomness