Engineering / Mathematics — Discrete Logarithms and Factoring
Smooth Numbers
Smooth numbers, their density, and why they are the raw material of subexponential factoring and index calculus.
Executive summary
An integer is smooth if all its prime factors are small. Smooth numbers factor easily over a fixed set of primes, which is what makes them useful in relation-collecting algorithms.
Their density governs the running time of every subexponential factoring and discrete logarithm method.
Learning objectives
- Define smoothness and state the density estimate.
- Explain the role of smooth numbers in relation collection.
- Derive the optimal smoothness bound.
01Definition and density
Smooth number
An integer is y-smooth if every prime factor is at most y.
Ψ(x, y) denotes the count of y-smooth integers up to x.
Density estimate
With u = ln x / ln y,
Ψ(x, y) / x ≈ u^{−u} = ρ(u),
where ρ is the Dickman function.
The estimate says smoothness becomes rare quickly as the ratio u grows. For u = 2 about a quarter of integers are smooth; for u = 10 the proportion is around 10^{−10}.
02Why smooth numbers are useful
A y-smooth number factors completely over the primes below y, so it can be recorded as an exponent vector over that fixed basis. Relations between such vectors are what the sieve algorithms collect.
Fix a factor base
All primes up to the smoothness bound y.
Generate candidates
Values whose smoothness can be tested cheaply, typically by sieving.
Keep the smooth ones
Each smooth value gives an exponent vector over the factor base.
Solve a linear system
Enough vectors give a linear dependence modulo 2, which yields a congruence of squares and hence a factorisation.
03Choosing the smoothness bound
Two costs oppose each other. A small bound makes smooth numbers rare, so relation collection is slow. A large bound makes the factor base big, so the linear algebra is slow.
- Small y
Relations rareCollection dominates; many candidates needed per relation - Large y
Factor base largeLinear algebra dominates; the matrix grows - Optimal y
L(1/2) or L(1/3)Balances the two; derived by differentiating the total cost
L_n(α, c) = exp((c + o(1))(ln n)^α (ln ln n)^{1−α})Balancing the two costs with the Dickman estimate gives the optimum, and the resulting total is subexponential — of the form L(1/2) for the quadratic sieve and L(1/3) for the number field sieve. That expression is the reason RSA moduli must be thousands of bits rather than hundreds.
04Frequently asked questions
Why is the density u^{−u} rather than something simpler?
It comes from a recursive count of integers whose largest prime factor is bounded, which produces the Dickman differential-delay equation. The u^{−u} form is its asymptotic behaviour and is accurate over the range that matters.
How is smoothness tested efficiently?
By sieving rather than by trial dividing each candidate. Sieving marks multiples of each factor base prime across an interval, so the cost is amortised over all candidates simultaneously.
Does the optimum depend on the algorithm?
Yes. The quadratic sieve and the number field sieve have different relation-generation costs, so their optimal bounds and resulting complexities differ — L(1/2) versus L(1/3).
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 336-337.
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.