Classical Factoring: Trial Division, Fermat and Lehman

Executive summary

Cheap methods first — they remove most of the work

Trial division by small primes removes small factors at negligible cost and is always the first stage of any factoring pipeline. Fermat's method attacks the opposite extreme, factoring quickly when the two factors are close together, by searching for a representation of n as a difference of squares. Lehman's method interpolates between them, guaranteeing a factor in O(n^1/3) operations — the identity behind Fermat is also the identity behind the quadratic sieve and the number field sieve.

Learning objectives

Implement trial division with a wheel and state its cost.
Apply Fermat's method and identify when it is fast.
Explain Lehman's multiplier trick and its complexity.
Describe the difference-of-squares identity common to modern sieves.
Order the stages of a practical factoring pipeline.

Section 01Trial division

Dividing by 2, 3, 5 and then by numbers coprime to them — a wheel — removes small factors efficiently. A wheel modulo 30 tests only 8 of every 30 candidates, a saving of more than 70% over testing all odd numbers.

AlgorithmTrial division with a modulus-30 wheelin: n → out: small prime factors and the remaining cofactor

Remove all factors of 2, 3 and 5 by repeated division.
Set d ← 7 and cycle the increments 4, 2, 4, 2, 4, 6, 2, 6. These skip every multiple of 2, 3 and 5.
While d² ≤ n: while d divides n, record d and divide it out.
Advance d by the next increment in the cycle.
If n > 1 after the loop, n itself is prime.

Where to stop

Trial division should be run to a fixed bound, not to √n. Beyond about 10⁶ every stronger method is faster per factor found. The purpose of this stage is to remove the many small factors cheaply, not to complete the factorisation.

Section 02Fermat's method

If n = ab with a, b both odd, then

n = x² − y² = (x − y)(x + y), x = (a+b)/2, y = (b−a)/2

So the search starts at x = ⌈√n⌉ and increments, testing whether x² − n is a perfect square. When the factors are close, y is small and the search terminates almost immediately.

Catastrophic when the factors are far apart

For n = 2p with p large, x must climb to roughly n/4 before y becomes an integer — worse than trial division. Fermat's method is a special-case tool, and its inclusion in a pipeline should be bounded by a small iteration budget.

But the identity is universal

Every modern general-purpose factoring algorithm — the continued fraction method, the quadratic sieve, the number field sieve — seeks a congruence x² ≡ y² (mod n) with x ≢ ±y, then takes gcd(x − y, n). They differ only in how the congruence is manufactured. Fermat's method is the direct, and worst, way of finding one.

Section 03Lehman's method

Lehman's improvement applies Fermat's search not to n but to kn for a range of small multipliers k. A suitable multiplier makes the two factors of kn nearly equal, which is exactly the case Fermat handles well.

O(n^1/3)guaranteed worst-case complexity

n^1/3trial division bound used first

Deterministicno randomisation, no failure mode

AlgorithmLehman's methodin: n → out: a non-trivial factor, or a proof of primality

Trial divide n by all integers up to n^1/3. This handles every factor below the bound.
For k = 1 to n^1/3:
For x in a short range starting at ⌈√(4kn)⌉:
If x² − 4kn is a perfect square y², then gcd(x + y, n) is a non-trivial factor.
If nothing is found, n is prime.

Historical significance

Lehman's method was the first to beat the √n barrier deterministically. It is superseded in practice by ρ, p−1 and ECM, but it remains the clean example of how a multiplier can reshape a problem into a favourable case.

Section 04The pipeline

Stage 01Trial divisionTo about 10⁶. Removes most factors at negligible cost.
Stage 02Perfect power testDetect n = m^k; several later methods misbehave on perfect powers.
Stage 03Compositeness testA strong probable prime test — there is no point factoring a prime.
Stage 04Mid-range methodsPollard ρ and SQUFOF for factors up to about 20 digits; p−1 for smooth cases.
Stage 05ECMFinds factors up to 50 or 60 digits, with cost governed by the factor size.
Stage 06SievesMPQS or the number field sieve, whose cost depends on the size of n itself.

Order matters, and so does recursion

Running a sieve before ECM wastes enormous effort when a mid-sized factor exists. Equally, each factor found must be tested for primality and the cofactor fed back through the pipeline — a composite cofactor left unfactored is a silently incomplete result.

ReferenceFrequently asked questions

Is trial division ever the best complete method?

For numbers up to about 12 digits, yes — a wheel with a precomputed prime table completes faster than the setup cost of any sophisticated method. Small-input performance matters because factoring routines are called recursively on cofactors.

Why test for perfect powers explicitly?

Because Pollard's rho degenerates on them, ECM can behave unpredictably, and the sieves assume a composite with distinct factors. The test costs almost nothing and prevents several failure modes at once.

Does Fermat's method have any modern use?

As a bounded check for the specific weakness of nearly-equal factors, which occasionally arises from poor RSA key generation. Run for a few thousand iterations it costs almost nothing and occasionally succeeds outright.

NavigateContinue in this stream

Curated next steps from this page. The site also surfaces algorithmically related reading below.

ProvenanceSources and further reading

This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.