Engineering / Mathematics — Primality Testing
Trial Division and Basic Primality Testing
Trial division as a primality test and as a filter, its exponential cost, and the role it still plays in practice.
Executive summary
Trial division tests primality by attempting division by every candidate factor up to the square root. It is correct, simple, and exponential in the input length.
It survives in practice not as a test but as a filter: rejecting candidates with small factors cheaply before an expensive test is applied.
Learning objectives
- State trial division and prove its correctness bound.
- Explain why it is exponential despite appearing polynomial.
- Size the filter bound for use ahead of Miller-Rabin.
01The method
Trial division
integer nprime, or composite with a factor- If n < 2, report composite or unit.
- For each candidate d = 2, 3, 5, 7, ... while d² ≤ n:
- If d divides n, report composite with factor d.
- Report prime.
O(√n) divisions = O(2^{ℓ/2}) in the bit length ℓSquare root bound
If n is composite then it has a prime factor not exceeding √n.
Reason. Write n = ab with 1 < a ≤ b. Then a² ≤ ab = n, so a ≤ √n, and any prime factor of a is at most a.
02Trial division as a filter
Its real use is eliminating candidates with small factors before an expensive probabilistic test. Most composites have a small factor, so a short division loop removes most of them for a fraction of one modular exponentiation.
| Filter bound | Odd candidates surviving | Cost per candidate |
|---|---|---|
| 3 only | ≈ 67% | One division |
| Primes below 100 | ≈ 12% | About 25 divisions |
| Primes below 1000 | ≈ 8% | About 168 divisions |
| Primes below 65536 | ≈ 5% | About 6500 divisions |
The survival proportion follows from Mertens' theorem as approximately e^{−γ}/ln y for bound y, and the diminishing returns are visible: going from 1000 to 65536 costs forty times the divisions to remove another three per cent.
03Where it remains the right tool
- Numbers small enough that
√nis trivially reachable — under a few billion, trial division against a sieved prime table is faster than any probabilistic test. - Filtering candidates in prime generation, as above.
- Completely factoring a number known to be smooth, where every factor is small by hypothesis.
- Extracting small factors before invoking a general factoring algorithm, which almost all such algorithms assume has been done.
A useful implementation trick: rather than dividing by each small prime, compute a single gcd against the product of all primes below the bound. One gcd replaces thousands of divisions, and the product is precomputed once.
04Frequently asked questions
Is trial division ever preferable to Miller-Rabin?
For small inputs, yes. Below roughly 2^32 a lookup against a sieved table or a short division loop beats a modular exponentiation. The crossover is where the square root cost exceeds the exponentiation cost.
Why divide only by primes rather than all integers?
Because a composite divisor's prime factors would have been found earlier. Dividing by primes only reduces the work by a factor of about ln n, at the cost of needing a prime table.
Does finding no factor below the square root prove primality?
Yes, unconditionally. Trial division is a proof, not a probabilistic test — which is why it remains the definitive method for small numbers despite its cost on large ones.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 244-245.
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.