Engineering/Mathematics/Algorithm engineering
Probabilistic Algorithms
Randomness buys simplicity and speed, and it is paid for with a failure probability that must be quantified rather than assumed away. The discipline is to state which model applies, prove the per-run error bound, and drive it down by repetition to a level below the ambient risk of hardware failure.
- Design method
- Computing
- Error analysis
- ≈15 min read
- Precedes primality testing
01
Executive summary
A probabilistic algorithm reads random bits along with its input. Two models matter. A Las Vegas algorithm always returns a correct answer, with running time a random variable. A Monte Carlo algorithm runs in a fixed time but may err with bounded probability.
Randomised algorithms dominate this field for one reason: for many problems the randomised solution is dramatically simpler and faster than any known deterministic one. Miller–Rabin decides compositeness in O(kℓ3) while the deterministic AKS test needs a far higher exponent; polynomial factorization over a finite field is easy with randomness and awkward without it.
| Model | Correctness | Running time | Example |
|---|---|---|---|
| Las Vegas | Always correct | Random; bounded in expectation | Random prime generation; Cantor–Zassenhaus with verification |
| Monte Carlo, one-sided | Errs in one direction only | Fixed | Miller–Rabin: never calls a prime composite |
| Monte Carlo, two-sided | May err either way | Fixed | Randomised approximation and sampling algorithms |
| Deterministic | Always correct | Fixed | AKS primality; trial division |
A Monte Carlo algorithm with an efficiently checkable answer converts into a Las Vegas algorithm by repeating until verification succeeds.
02
Models and error reduction
One-sided error
An algorithm for a decision problem has one-sided error if a “yes” answer is always correct and a “no” answer errs with probability at most ε — or the reverse. Miller–Rabin has this shape: an output of composite is accompanied by a witness and is certain, whereas probably prime carries the error.
- Two-sided error needs a majority vote. With per-run error ε < 1/2, taking the majority of k runs reduces error exponentially by a Chernoff bound, but requires more runs than the one-sided case for the same target.
- Independence is a requirement, not a formality. Reusing the same random bases, or drawing from a weak generator, invalidates the compounding argument entirely. Miller–Rabin with a fixed base set is a deterministic test with different — and adversarially exploitable — properties.
- Choose the target relative to ambient risk. Beyond about 2−80, the dominant failure mode is no longer the algorithm but undetected hardware error, so further rounds buy nothing measurable.
03
Generating random values correctly
Uniform selection from a range
Producing a uniform value in [0,n) from a stream of random bits is the most frequently botched primitive in cryptographic code.
| Method | Bias | Cost | Verdict |
|---|---|---|---|
| r mod n for ℓ-bit r, ℓ = len(n) | Up to a factor of two on some values | One draw | Unacceptable |
| r mod n with ℓ = len(n) + 64 | Statistical distance ≤ n/2ℓ ≈ 2−64 | One draw | Acceptable for most purposes |
| Rejection sampling | Exactly zero | Expected < 2 draws | Preferred where exactness is specified |
| Lemire's multiply-and-shift | Exactly zero with a rare correction | One multiply, rarely a retry | Fast and exact for word-size ranges |
Rejection sampling: draw ℓ = len(n) bits; if the result is ≥ n, discard and redraw. The acceptance probability exceeds 1/2, so the expected number of draws is below 2.
Sampling structured objects
Random prime
Draw random odd candidates, pre-sieve by small primes, apply Miller–Rabin. Expected O(ℓ) candidates by the prime density estimate.
Random invertible element
Draw uniformly from [1,n) and check gcd = 1. Success probability φ(n)/n, which is bounded below by roughly 1/(6 ln ln n).
Random generator of a group
For a cyclic group of order m with known factorization, draw and test gm/q ≠ 1 for each prime q ∣ m. Success probability φ(m)/m.
Random factored integer
Bach's algorithm produces a uniform integer in a range together with its factorization, in expected polynomial time — remarkable, because factoring a given integer is hard.
Why random factored numbers are interesting
Bach's algorithm sidesteps the hardness of factoring by generating the factorization first and the number second, then correcting the distribution by rejection. It is the standard tool for building test instances with known structure and for constructions that need a uniform integer whose factorization is available to the analysis.
04
Random prime generation as a worked example
Fix the target size and any structural constraints
For example, a 1024-bit prime with the top two bits set, so that a product of two such primes has exactly 2048 bits.
Draw a random odd candidate
Use a cryptographic random source; set the top bits to fix the size and the bottom bit to force oddness.
Pre-sieve by small primes
Reject candidates divisible by primes below a bound around 1000. This removes roughly 80% of them at negligible cost and dominates the practical speed-up.
Apply Miller–Rabin with random bases
Enough rounds to reach the target error. For random candidates the effective error is far below the worst-case 4−k.
Optionally certify
Where a proof is required rather than a bound, use a Pocklington certificate when the factorization of p−1 is available, or an ECPP-style primality proof.
Check any extra conditions
For RSA: gcd(e, p−1) = 1. For discrete-log parameters: q ∣ p−1 for the intended subgroup order.
The random source is the weakest link
Every analysis on this page assumes independent uniform bits. Historical failures — insufficient entropy at boot on embedded devices, a flawed generator in a widely deployed library — produced colliding primes across thousands of independent devices, allowing keys to be recovered by simply taking gcds of published moduli. The mathematics was correct; the sampling was not.
05
When determinism is required
| Randomised algorithm | Deterministic option | Cost of determinism |
|---|---|---|
| Miller–Rabin | AKS primality test | Polynomial but far slower in practice |
| Miller–Rabin | Fixed base set for bounded inputs | Proven correct only below verified thresholds — a valid and fast choice for 64-bit inputs |
| Finding a quadratic non-residue | Trial search from small values | Polynomial only under the extended Riemann hypothesis |
| Cantor–Zassenhaus factorization | Berlekamp with exhaustive search | Exponential in the number of factors, or conditional on ERH |
| Random prime generation | Search upward from a fixed point | No proven bound on the search length without conjectures on prime gaps |
A recurring pattern: the deterministic version exists but its analysis is either conditional on an unproved hypothesis or carries a much worse exponent.
- Verified thresholds are genuinely useful. For n < 3.3 × 1024, testing the first thirteen prime bases makes Miller–Rabin deterministic and provably correct — exhaustively verified, not conjectural. Small-integer primality should use this rather than random bases.
- Reproducibility can be obtained without determinism by deriving the random bits from a seed and recording it. This keeps the probabilistic analysis intact while making runs replayable for debugging and audit.
- Verification often beats derandomisation. If an answer can be checked cheaply, a Monte Carlo algorithm plus a verifier gives a Las Vegas algorithm with certainty and almost no added cost — the right pattern for polynomial factorization and for Wiedemann's algorithm.
06
Quick reference and FAQ
| Rule | Reason |
|---|---|
| State the model explicitly | Las Vegas and Monte Carlo have incompatible guarantees |
| Prove a per-run error bound | Repetition arguments require a numeric starting point |
| Use independent randomness per run | Compounding fails otherwise |
| Verify when verification is cheap | Converts bounded error into certainty |
| Sample without bias | Rejection sampling, or an excess of at least 64 bits |
| Separate the entropy source from the algorithm | The analysis assumes uniform independent bits and inherits any defect in them |
| Target error below ambient hardware risk | Additional rounds beyond that point are not measurable |
How many Miller–Rabin rounds are actually needed?
Is a pseudorandom generator sufficient?
What does it mean for an algorithm to have expected polynomial time?
Can the error probability ever be driven to zero?
08
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 7.
- R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge, 1995.
- E. Bach, 'How to generate factored random numbers', SIAM J. Comput. 17 (1988) 179–193.
- N. Heninger et al., 'Mining your Ps and Qs: detection of widespread weak keys in network devices', USENIX Security, 2012.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: probabilistic-algorithmsReview cycle: annual