Engineering / Mathematics — Discrete Logarithms and Factoring
Better Smoothness Density Estimates
Refined estimates for smooth number density and how they determine optimal sieve parameters.
Executive summary
The crude Dickman estimate is enough to derive the asymptotic complexity of sieve algorithms, but not to choose parameters for a specific factorisation.
Practical parameter selection uses refined estimates together with empirical calibration, because the optimum is flat near its minimum and the asymptotics hide substantial constants.
Learning objectives
- State the refined smoothness estimates.
- Derive the optimal smoothness bound.
- Explain why empirical calibration remains necessary.
01Refining the estimate
The Dickman function ρ(u) satisfies a differential-delay equation and its asymptotic u^{−u} is accurate only to within factors that matter in practice.
ρ(u) = u^{−u(1 + o(1))}, with the o(1) term significant for the u values arising in practiceFor sieve algorithms the relevant u is typically between 2 and 5, where the asymptotic form is noticeably off. Numerical evaluation of the Dickman function, or tabulated values, is used instead.
02Deriving the optimal bound
Write the total cost
Cost of collecting relations plus cost of the linear algebra, both as functions of the smoothness bound y.
Express relation cost
Number of candidates needed is proportional to 1/ρ(u), with u = ln n / ln y.
Express algebra cost
Roughly the square or a low power of the factor base size, which is π(y).
Minimise
Differentiate the sum with respect to y and solve, giving y of the form L(1/2) or L(1/3).
The resulting optimum is what produces the subexponential complexity. The derivation is the reason those particular exponents appear rather than any others.
- Quadratic sieve
y ≈ L(1/2, 1/2)Total cost L(1/2, 1) - Number field sieve
y ≈ L(1/3, c)Total cost L(1/3, 1.92)
03Why calibration is still needed
Serious implementations tune parameters empirically against the target size, using the theory to locate the neighbourhood and measurement to find the point within it.
| Parameter | Set by | Sensitivity |
|---|---|---|
| Smoothness bound | Theory plus calibration | Flat near optimum; costly if far off |
| Sieve interval length | Memory and cache size | Hardware dependent |
| Large prime bounds | Empirical | Substantial gains from partial relations |
| Polynomial selection | Extensive search | Among the highest-value choices in NFS |
Polynomial selection in the number field sieve is worth singling out: a substantial fraction of total effort is spent searching for a good polynomial before sieving begins, because the choice affects the smoothness rate of every candidate that follows.
04Frequently asked questions
Why is the cost curve flat near the optimum?
Because the two opposing costs cross at a shallow angle — one rising and one falling smoothly. That flatness is forgiving of imprecise parameter choice, which is why rough calibration suffices in practice.
Are large primes worth allowing?
Yes, substantially. Permitting one or two primes above the smoothness bound in a relation produces partial relations that combine into full ones, and this yields large practical gains at little cost.
Does polynomial selection affect the asymptotic complexity?
Only in the constant, but that constant is significant. A better polynomial improves smoothness rates across the entire sieving phase, so the search effort pays back many times over.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 352-354.
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.