Engineering / Mathematics — Computation and Sources
Arbitrary Precision Arithmetic in Practice
Implementation concerns for multiprecision arithmetic: memory management, algorithm dispatch, and constant-time requirements.
Executive summary
A production multiprecision library is dominated by concerns that never appear in the mathematics: allocation strategy, crossover tuning, cache behaviour and side-channel discipline.
The asymptotically best algorithm is frequently the wrong choice at the sizes that matter.
Learning objectives
- Identify the main implementation concerns.
- Understand algorithm dispatch by operand size.
- State the constant-time requirements.
01Memory and representation
- Allocation strategy. Multiprecision operations produce results of varying size, so either every operation allocates or the caller supplies a buffer. The latter is faster and harder to use correctly.
- Small value optimisation. Most integers in a typical workload fit a single word, so libraries special-case them to avoid allocation entirely.
- Normalisation invariants. Leading zeros stripped, canonical zero, digits in range — enforced after every operation, and the source of subtle bugs when missed.
- Aliasing. Operations where an output shares storage with an input must either detect the aliasing or be written to tolerate it.
02Algorithm dispatch
A library implements several algorithms per operation and dispatches on operand size, since asymptotic superiority only applies beyond a crossover.
- Single word
Direct machine instructionNo multiprecision path at all - Small
SchoolbookBest below the Karatsuba crossover - Medium
Karatsuba, then Toom-CookSeveral crossovers in sequence - Large
FFT-basedCrossover in the tens of thousands of bits
Mature libraries tune these thresholds automatically at build time by benchmarking, which is the only reliable approach across diverse hardware.
03Constant-time arithmetic
Cryptographic use imposes requirements that conflict with the optimisations above.
| Ordinary implementation | Constant-time requirement |
|---|---|
| Early exit on comparison | Always scan the full operand |
| Skip leading zero words | Process a fixed number of words |
| Branch on the sign | Compute both paths and select without branching |
| Extended Euclid for inversion | Fixed-iteration variant or Fermat exponentiation |
| Square-and-multiply | Always-multiply or Montgomery ladder |
| Table lookup by exponent digit | Scan the whole table with masked selection |
This is why cryptographic arithmetic is generally implemented separately from general-purpose arithmetic, often in assembly, rather than sharing a common library. The two have incompatible optimisation criteria.
04Frequently asked questions
Why not always use the asymptotically fastest algorithm?
Because crossovers are high. Using an FFT method at 2048 bits would be far slower than schoolbook, and the asymptotic advantage never materialises at cryptographic sizes.
Can constant-time code be verified automatically?
Partially. Tools exist that check for secret-dependent branches and memory accesses at the binary level, and they are used in serious cryptographic libraries. They are not a complete guarantee.
Is the performance cost of constant-time code significant?
Meaningful but acceptable — typically a factor of two or so for the affected operations. Given that the alternative is key leakage, the trade is not a close call.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — orientation page, no single source section.
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.
Forward reference: this page extends beyond the source text and is flagged as post-source.
Author: Kevin Jogin. Last reviewed 2026-08-07.