Engineering / Mathematics — Primality Testing
Trial Division up to a Small Bound
Choosing the trial division bound ahead of a probabilistic test, and the cost balance that determines it.
Executive summary
Trial division ahead of Miller-Rabin removes most composites cheaply. How far to divide is an optimisation with a clear structure: division cost rises linearly in the bound while the rejection rate improves only logarithmically.
Mertens' theorem supplies the survival rate, making the optimum computable rather than guessed.
Learning objectives
- Quantify the survival rate as a function of the bound.
- Balance division cost against saved exponentiations.
- Implement the filter efficiently.
01Survival rate
The proportion of odd integers with no prime factor below y follows from Mertens' theorem.
survival ≈ 2 e^{−γ} / ln y (the factor 2 because even numbers are excluded already)| Bound y | Primes below y | Odd candidates surviving |
|---|---|---|
| 100 | 25 | ≈ 24% |
| 1,000 | 168 | ≈ 16% |
| 10,000 | 1,229 | ≈ 12% |
| 65,536 | 6,542 | ≈ 10% |
02The cost balance
Cost of filtering
Roughly π(y) single-precision divisions per candidate, or one multiprecision gcd.
Cost of a Miller-Rabin round
One modular exponentiation, O(len(n)³) — thousands of times more expensive.
Expected total
candidates × filter cost + survivors × exponentiation cost.
Optimise
Increase y while the marginal reduction in survivors saves more than the added divisions cost.
Because an exponentiation costs so much more than a division, the optimum sits well beyond where the survival curve has flattened. Bounds in the low thousands to tens of thousands are typical, and the optimum is broad — anywhere in that range performs within a few per cent of the best.
For larger moduli the balance shifts upward, since the exponentiation cost grows cubically in the bit length while the division cost is roughly constant.
03Efficient implementation
Rather than dividing by each small prime in turn, compute a single gcd against a precomputed product.
Filter by gcd against a primorial
candidate n, precomputed primorial Preject, or pass to Miller-Rabin- Precompute P = product of all primes in (2, y].
- For each candidate n:
- Compute g = gcd(n, P).
- If g ≠ 1, reject n as composite.
- Otherwise pass n to the probabilistic test.
one gcd, O(len(n) · len(P))A further refinement used in incremental search: compute the residue of a base candidate against each small prime once, then update the residues by addition as the candidate is stepped, avoiding a fresh division per step. This is the standard sieve-based generation technique.
04Frequently asked questions
Why exclude 2 from the primorial?
Because candidates are already odd by construction. Including 2 would make every gcd even and reject everything.
Is one large gcd really faster than many small divisions?
For multiprecision candidates, yes, because the divisions are all multiprecision-by-single-precision and there are thousands of them. The gcd is a single operation on operands of comparable size.
Does the optimum depend on the Miller-Rabin round count?
Only weakly. Most rejected candidates fail on the first round, so the marginal cost of a survivor is roughly one exponentiation regardless of how many rounds a survivor would eventually receive.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 255-258.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.