Orientation
Algorithm Notation and Complexity Conventions
The notation, cost model and complexity conventions used throughout this collection, including the sub-exponential L-function.
Engineering / MathematicsOrientation3 min readKV-MATH-0502
Cost statements in computational number theory are only meaningful relative to a stated model. This page fixes the conventions used everywhere else in the collection.
The cost model
Costs are counted in bit operations unless stated otherwise. The alternative — counting arithmetic operations on machine words — hides exactly the growth that dominates in this subject, because the numbers involved routinely exceed a machine word by orders of magnitude.
Conventions
Asymptotic notation
- O(f(n))
- Bounded above by a constant multiple of f(n) for large n. The default in this collection.
- Omega(f(n))
- Bounded below similarly.
- Theta(f(n))
- Bounded both above and below.
- o(f(n))
- Grows strictly slower than f(n).
- Soft-O
- Written with a tilde; suppresses logarithmic factors. Useful when those factors are not the point.
The sub-exponential L-function
Integer factorisation and class group computation both run in time that is neither polynomial nor exponential in the input size. The standard notation for this middle range is:
The parameter a is what matters. It interpolates between the two familiar regimes and gives a single scale on which to compare methods.
| Value of a | Regime | Example |
|---|---|---|
| a = 0 | Polynomial in log N | Modular exponentiation |
| a = 1/2 | Classic sub-exponential | Quadratic sieve, ECM, class group methods |
| a = 1/3 | Improved sub-exponential | Number field sieve |
| a = 1 | Exponential in log N | Trial division |
Probabilistic and conditional results
Three qualifiers appear repeatedly and are not interchangeable.
Las Vegas
Always correct when it terminates; running time is random. Cantor-Zassenhaus splitting is of this type.
Monte Carlo
Fixed running time; may return a wrong answer with bounded probability. A single Fermat test is of this type.
Conditional on GRH
Correctness or complexity depends on an unproven hypothesis. The result is real but its status differs from an unconditional one.
Heuristic complexity
Several headline complexities in this subject are heuristic: they rest on plausible but unproven assumptions about how often values produced by an algorithm are smooth. The number field sieve's L(1/3) bound is of this kind. These estimates match observed behaviour closely, which is why they are quoted, but they are not theorems.
Frequently Asked Questions
Why count bit operations rather than machine operations?
What does o(1) mean inside the L-function?
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.