Engineering/Mathematics/Algorithm engineering
Multiprecision Integer Arithmetic
Every algorithm in this library is ultimately a sequence of big-integer operations, and modular exponentiation dominates almost all of them. Improving the inner multiply-and-reduce loop by a constant factor improves an entire cryptographic system by that same factor.
- Implementation core
- Computing
- Performance critical
- ≈17 min read
- Underpins every other algorithm
01
Executive summary
A multiprecision integer is an array of machine words in base 2w, with a separate sign. Addition and subtraction are linear and uninteresting; multiplication, division and modular reduction are where all the engineering lies.
Three decisions determine performance. Which multiplication algorithm applies at the operand size in question. How modular reduction is performed — trial division, Barrett, or Montgomery. And how exponentiation is sequenced, since the exponentiation loop determines how many multiplications and reductions occur at all. For cryptographic code a fourth constraint applies throughout: the execution path must not depend on secret data.
02
Representation
- Base. Store digits in base 2w where w is 32 or 64. A full-width base requires access to the high half of a word product — available as a widening multiply on most architectures. Some libraries use a reduced radix such as 251 or 226 to allow lazy carry propagation and to exploit floating-point or vector units.
- Sign. Sign–magnitude is standard for arbitrary-precision integers, because two's complement has no natural fixed width. Comparison then reduces to a length check followed by a digit-wise scan from the most significant end.
- Normalisation. Maintain the invariant that the top digit is non-zero, so that length equals significance. Failing to normalise after a subtraction is a classic source of subtle bugs in comparison and division routines.
- Length and size. The bit length is ℓ = (d−1)w + ⌈log2(top digit + 1)⌉ for d digits. Every complexity bound in this library is expressed in terms of this quantity.
03
Multiplication
| Algorithm | Complexity | Idea | Practical range |
|---|---|---|---|
| Schoolbook | O(ℓ2) | Digit-by-digit with carry accumulation | Up to a few hundred bits; best constants |
| Karatsuba | O(ℓ1.585) | Three half-size products via (a0+a1)(b0+b1) | Roughly 300–10,000 bits |
| Toom–Cook (Toom-3) | O(ℓ1.465) | Evaluate, multiply pointwise, interpolate | Thousands of bits |
| Schönhage–Strassen | O(ℓ log ℓ log log ℓ) | FFT over a ring of the form ℤ/(2k+1) | Tens of thousands of bits and up |
| Harvey–van der Hoeven | O(ℓ log ℓ) | Multidimensional FFT construction | Theoretical; galactic crossover |
Squaring is a special case worth implementing separately: half the digit products are duplicated, giving roughly a 30–40% saving over a general multiply.
The Karatsuba identity
Division is the expensive primitive
Classical division with remainder is O(ℓ2) like multiplication, but with much worse constants: each step requires a quotient-digit estimate and a correction. This asymmetry is the entire motivation for Montgomery and Barrett reduction, both of which replace division by multiplication and shifting.
04
Modular reduction
Trial division
Compute a mod n directly by long division. Correct, simple, and the slowest option. Acceptable when reductions are rare relative to other work.
Barrett reduction
Precompute μ = ⌊B2k/n⌋ once, then estimate the quotient with two multiplications and correct by at most two subtractions. Best when inputs are arbitrary and the modulus is reused.
Montgomery reduction
Work with residues scaled by R = 2wk. Reduction becomes multiply, add, shift — no division at all. Best when many operations share one modulus, as in exponentiation.
Special-form moduli
Pseudo-Mersenne primes such as 2255−19 reduce by a shift and a multiply-by-small-constant. This is why modern curve parameters are chosen with that shape.
Montgomery multiplication of a, b < n (n odd, R = 2^{wk} > n)
- precompute n′ = −n^{-1} mod 2^w (one extended gcd, done once per modulus)
- T ← a·b // Montgomery-domain operands
- for i = 0 .. k−1:
- m ← (T mod 2^w)·n′ mod 2^w
- T ← (T + m·n·2^{wi}) / 2^w // exact division: the low word is zero by construction
- if T ≥ n: T ← T − n
- return T // equals a·b·R^{-1} mod n
2k² + O(k) word multiplications for a k-word modulus — the same order as one schoolbook multiplication, with no division. Conversion into and out of the Montgomery domain costs one extra multiplication each way, amortised over the whole exponentiation.
The final conditional subtraction is a side channel
The last step of Montgomery reduction executes only sometimes, and whether it executes depends on the operands. In secret-key code this must be made unconditional — for example by always performing the subtraction into a scratch buffer and selecting the result with a constant-time mask. The same discipline applies to every branch and every table index in the exponentiation loop.
05
Modular exponentiation
Exponentiation is the dominant cost in RSA, Diffie–Hellman and primality testing, so its structure matters more than any other single choice.
| Method | Multiplications | Memory | Notes |
|---|---|---|---|
| Left-to-right binary | ℓ squarings + ℓ/2 multiplications on average | O(1) | Simplest; the baseline |
| Fixed window, width k | ℓ squarings + ℓ/k multiplications | 2k precomputed values | Window 4–6 is typical at 2048 bits |
| Sliding window | ℓ squarings + about ℓ/(k+1) multiplications | 2k−1 values | Better than fixed window; variable pattern leaks unless equalised |
| Montgomery ladder | ℓ squarings + ℓ multiplications | O(1) | Uniform operation sequence; the standard constant-time choice |
| CRT exponentiation (RSA) | two half-size exponentiations | two moduli | About a fourfold speed-up for private operations |
Counts are modular multiplications; each costs O(ℓ²) bit operations classically, giving the familiar O(ℓ³) total.
- Combine CRT with windowing. The RSA private operation should use CRT to halve the operand size and windowing within each half; the two optimisations multiply.
- Guard the CRT recombination. A fault during one of the two half-exponentiations lets an attacker recover the factorization from a single incorrect signature. Verify the signature before releasing it, or recompute and compare.
- Blind the exponent and the base when the exponent is secret: replace d by d + r·λ(n) and the base by rex, then correct at the end. This defeats timing and simple power analysis that target the exponent bits.
- Never branch on secret data — including table indices, which leak through cache timing. Scatter–gather or full-table scanning is required for window methods on secret exponents.
06
Engineering checklist
| Area | Check | Failure mode if skipped |
|---|---|---|
| Carry handling | Exhaustive tests at word boundaries and all-ones patterns | Rare, data-dependent wrong answers |
| Normalisation | Top digit non-zero after every operation | Comparison and division errors |
| Negative operands | Sign handling in subtraction, division and modular reduction | Wrong sign of remainder; silent corruption |
| Zero and one | Degenerate inputs to every routine | Crashes or infinite loops in division |
| Modulus parity | Montgomery requires an odd modulus | Silent incorrect results |
| Constant time | No secret-dependent branches, indices or loop counts | Timing and cache side channels |
| Memory hygiene | Zeroing intermediate buffers | Key material recoverable from freed memory |
| Cross-validation | Differential testing against a reference library | Undetected algorithmic errors |
A note on building versus adopting
Mature libraries — GMP for general work, and hardened cryptographic libraries for key operations — encode decades of correctness and side-channel experience. Writing a multiprecision layer is an excellent way to understand the algorithms and a poor way to obtain production cryptography. Where a custom implementation is unavoidable, differential testing against a reference implementation across millions of random inputs is the minimum acceptable validation.
07
Quick reference and FAQ
| Operation | Classical | With fast multiplication |
|---|---|---|
| Add, subtract | O(ℓ) | O(ℓ) |
| Multiply | O(ℓ2) | Õ(ℓ) |
| Square | O(ℓ2), ≈0.6× multiply | Õ(ℓ) |
| Divide with remainder | O(ℓ2) | Õ(ℓ) |
| Modular multiply (Montgomery) | O(ℓ2) | Õ(ℓ) |
| Modular exponentiation | O(ℓ3) | Õ(ℓ2) |
| gcd | O(ℓ2) | Õ(ℓ) |
| Base conversion | O(ℓ2) | Õ(ℓ) |
At what size does Karatsuba actually beat schoolbook?
Why is Montgomery multiplication preferred over Barrett for exponentiation?
Does Montgomery work with an even modulus?
How much does the CRT optimisation really save in RSA?
09
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 3.
- D. E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed., Addison-Wesley, 1997 — §4.3, the classical reference on multiprecision arithmetic.
- P. L. Montgomery, 'Modular multiplication without trial division', Math. Comp. 44 (1985) 519–521.
- R. P. Brent and P. Zimmermann, Modern Computer Arithmetic, Cambridge, 2010.
- P. C. Kocher, 'Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems', CRYPTO '96, LNCS 1109, 104–113.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: multiprecision-integer-arithmeticReview cycle: annual