Fast Integer & Modular Arithmetic

Intuition, Vocabulary and Foundations

Large integers are arrays of limbs. In base $B$,

$$x=\sum_{i=0}^{n-1}x_iB^i,\qquad 0\le x_i\lt B.$$

For $B=1000$, $12{,}345{,}678$ is $[678,345,12]$ in little-endian form. Carry propagation replaces a raw total $t_i$ by $t_i\bmod B$ and adds $\lfloor t_i/B\rfloor$ to the next limb. A canonical representation has normalized limbs and no unnecessary leading zeros.

Schoolbook multiplication accumulates every $x_iy_j$ at position $i+j$, costing $O(nm)$. Faster methods reduce recursive multiplications but add splitting, interpolation, allocation, and normalization overhead. Modular reduction is another major cost: Barrett approximates division with a reciprocal, while Montgomery changes representation so division by a power-of-two radix becomes a shift.

A limb array is valid only when every limb is normalized and its length is canonical. Optimized backends may use redundant intermediates, but every public boundary must restore the exact integer and these representation invariants.

Concept	Definition	Example	Boundary	Question answered
Limb representation	$x=\sum_i x_iB^i$	$12{,}345{,}678\leftrightarrow[678,345,12]$ in base $1000$	A limb equal to $B$ is not normalized	How is a large integer stored?
Carry propagation	Move multiples of $B$ upward	$1500$ becomes $[500,1]$	Dropping carry changes the value	How are raw totals normalized?
Schoolbook product	Accumulate all $x_iy_j$	Long multiplication	Quadratic work dominates at scale	What is the trusted baseline?
Karatsuba	Three half-size products	Beats four recursive products	Overhead loses on small inputs	How is subquadratic multiplication obtained?
Barrett reduction	Reciprocal-based quotient estimate	Fixed-modulus reduction	Bounds must limit correction work	How is division avoided?
Montgomery form	Store $xR\bmod m$	Repeated odd-modulus products	Requires $\gcd(R,m)=1$	How are shifts used for reduction?

Step-by-Step Derivations and Algorithms

Split $x=x_0+x_1B^h$ and $y=y_0+y_1B^h$. Karatsuba computes

$$z_0=x_0y_0,\quad z_2=x_1y_1,\quad z_1=(x_0+x_1)(y_0+y_1)-z_0-z_2,$$

then reconstructs $xy=z_0+z_1B^h+z_2B^{2h}$. The recurrence $T(n)=3T(n/2)+O(n)$ gives $O(n^{\log_2 3})$.

Toom-Cook generalizes this evaluation/interpolation idea. FFT multiplication converts limb products to convolution, then rounds or reconstructs coefficients before carrying.

For Montgomery arithmetic choose $R=2^w\gt m$ with odd $m$, and $m'\equiv-m^{-1}\pmod R$. Given $t$, set $q\equiv tm'\pmod R$ and $u=(t+qm)/R$. The numerator is divisible by $R$, and $u\equiv tR^{-1}\pmod m$.

Fast Integer & Modular Arithmetic algorithm map

flowchart TD
    A["Inspect operand size and workload"] --> B{"Integer or modular?"}
    B -->|"Integer"| C{"Limb count?"}
    C -->|"Small"| D["Schoolbook"]
    C -->|"Medium"| E["Karatsuba or Toom-Cook"]
    C -->|"Large"| F["FFT or NTT"]
    D --> G["Carry and normalize"]
    E --> G
    F --> G
    B -->|"Modular"| H{"Repeated odd modulus?"}
    H -->|"No"| I["Direct or Barrett"]
    H -->|"Yes"| J["Montgomery domain"]
    G --> K["Verify with oracle"]
    I --> K
    J --> K

Karatsuba preserves the exact split identity while replacing four recursive products with three. Barrett bounds quotient-estimation error; Montgomery makes $t+qm$ divisible by $R$ and preserves congruence after multiplying by $R^{-1}$. Crossover thresholds must be measured, not guessed from asymptotics.

Implementation, Complexity and Engineering

The reference provides canonical limb conversion, schoolbook multiplication, recursive Karatsuba, Barrett reduction, and Montgomery multiplication. Python integers serve as an independent result oracle.

from dataclasses import dataclass
from random import Random

BASE = 1 << 16

def normalize(limbs, base=BASE):
    if base <= 1 or any(x < 0 for x in limbs): raise ValueError("bad limbs")
    out, carry = (limbs[:] or [0]), 0
    for i in range(len(out)):
        total = out[i] + carry
        out[i], carry = total % base, total // base
    while carry: out.append(carry % base); carry //= base
    while len(out) > 1 and out[-1] == 0: out.pop()
    return out

def to_limbs(value, base=BASE):
    if value < 0: raise ValueError("nonnegative magnitude required")
    if value == 0: return [0]
    out = []
    while value: out.append(value % base); value //= base
    return out

def from_limbs(limbs, base=BASE):
    value = 0
    for limb in reversed(normalize(limbs, base)): value = value * base + limb
    return value

def schoolbook(a, b, base=BASE):
    a, b = normalize(a, base), normalize(b, base)
    if a == [0] or b == [0]: return [0]
    out = [0] * (len(a) + len(b))
    for i, x in enumerate(a):
        for j, y in enumerate(b): out[i + j] += x * y
    return normalize(out, base)

def karatsuba(a, b, threshold=128):
    if a < 0 or b < 0:
        sign = -1 if (a < 0) ^ (b < 0) else 1
        return sign * karatsuba(abs(a), abs(b), threshold)
    if not a or not b: return 0
    bits = max(a.bit_length(), b.bit_length())
    if bits <= threshold: return a * b
    half = bits // 2; mask = (1 << half) - 1
    a0, a1, b0, b1 = a & mask, a >> half, b & mask, b >> half
    z0 = karatsuba(a0, b0, threshold)
    z2 = karatsuba(a1, b1, threshold)
    z1 = karatsuba(a0 + a1, b0 + b1, threshold) - z0 - z2
    return z0 + (z1 << half) + (z2 << (2 * half))

@dataclass
class Barrett:
    modulus: int
    def __post_init__(self):
        if self.modulus <= 0: raise ValueError("positive modulus required")
        self.shift = max(1, self.modulus.bit_length())
        self.radix = 1 << self.shift
        self.reciprocal = self.radix * self.radix // self.modulus
    def reduce(self, value):
        if value < 0 or value >= self.radix * self.radix: return value % self.modulus
        q = value * self.reciprocal >> (2 * self.shift)
        r = value - q * self.modulus
        while r < 0: r += self.modulus
        while r >= self.modulus: r -= self.modulus
        return r
    def multiply(self, a, b): return self.reduce((a % self.modulus) * (b % self.modulus))

@dataclass
class Montgomery:
    modulus: int
    def __post_init__(self):
        if self.modulus <= 0 or self.modulus % 2 == 0: raise ValueError("positive odd modulus required")
        self.shift = self.modulus.bit_length(); self.radix = 1 << self.shift
        self.mask = self.radix - 1
        self.neg_inverse = (-pow(self.modulus, -1, self.radix)) & self.mask
    def reduce(self, value):
        q = ((value & self.mask) * self.neg_inverse) & self.mask
        result = (value + q * self.modulus) >> self.shift
        return result - self.modulus if result >= self.modulus else result
    def encode(self, value): return value % self.modulus * self.radix % self.modulus
    def decode(self, value): return self.reduce(value)
    def multiply(self, a, b): return self.reduce(a * b)

if __name__ == "__main__":
    assert to_limbs(12_345_678, 1000) == [678,345,12]
    assert from_limbs([678,345,12], 1000) == 12_345_678
    rng = Random(7)
    for _ in range(200):
        a, b = rng.getrandbits(512), rng.getrandbits(512)
        assert from_limbs(schoolbook(to_limbs(a), to_limbs(b))) == a * b
        assert karatsuba(a, b, 64) == a * b
    modulus = 1_000_000_007
    barrett, mont = Barrett(modulus), Montgomery(modulus)
    for _ in range(200):
        a, b = rng.randrange(modulus), rng.randrange(modulus)
        expected = a * b % modulus
        assert barrett.multiply(a, b) == expected
        assert mont.decode(mont.multiply(mont.encode(a), mont.encode(b))) == expected
    print("all tests passed")

Method	Cost	Regime	Requirement	Failure mode	Mitigation
Schoolbook	$O(n^2)$	Small operands	Wide accumulators	Overflow	Bound and normalize safely
Karatsuba	$O(n^{\log_2 3})$	Medium operands	Scratch space	Threshold too low	Benchmark crossover
Toom-Cook	Variant-dependent subquadratic	Larger operands	Exact interpolation	Nonexact division	Assert divisibility
FFT or NTT	Quasilinear transform cost	Very large operands	Error or CRT plan	Wrong coefficient	Prove numeric bounds
Barrett	Wide products and corrections	Fixed modulus	Reciprocal	Bad correction bound	Derive and assert bounds
Montgomery	Products, shifts, additions	Long odd-modulus chains	Encoded values	Mixing domains	Use explicit types

Applications, Case Studies and Exercises

Fast arithmetic supports cryptography, computer algebra, scientific computation, and primality testing. Backend selection depends on operand size, reuse, cache behavior, allocation, and side-channel requirements.

Practice

Apply Fast Integer & Modular Arithmetic

Carry trace: in base $1000$, multiply $[999,999]$ by itself, propagate carries, reconstruct the integer, and compare with $999{,}999^2$. Every final limb must lie between $0$ and $999$.

Modular backend: benchmark $100{,}000$ Barrett and Montgomery products modulo $1{,}000{,}000{,}007$. Measure Montgomery both including and excluding conversion cost; verify every sample against direct reduction.

Hands-on harness: compare schoolbook, Karatsuba, and the language's trusted product through $16{,}384$ bits. Test zeros, maximum limbs, uneven lengths, and radix powers. Report median latency, allocation, and measured thresholds.

Exercises: convert decimal values to base-$2^{16}$; prove Karatsuba; derive accumulator bounds; implement signed magnitudes; trace Montgomery reduction; implement Toom-3; design a timing-leak experiment.

Use schoolbook for small values, Karatsuba or Toom-Cook after measured crossovers, and transforms only at large sizes. Prefer Barrett for reciprocal reduction and Montgomery for long chains under one odd modulus; keep a trusted oracle and treat constant-time behavior as a separate requirement.

Next in the Series

In Elliptic Curves & Cryptographic Foundations, we'll explore Connect finite-field groups to modern cryptographic primitives..

PreviousFinite Fields & Polynomial Factorization Next Elliptic Curves & Cryptographic Foundations

Cookie Consent

Fast Integer & Modular Arithmetic

Table of Contents

Intuition, Vocabulary and Foundations

Step-by-Step Derivations and Algorithms

Implementation, Complexity and Engineering

Applications, Case Studies and Exercises

Apply Fast Integer & Modular Arithmetic

Next in the Series

Cookie Consent

Fast Integer & Modular Arithmetic

Table of Contents

Intuition, Vocabulary and Foundations

Step-by-Step Derivations and Algorithms

Implementation, Complexity and Engineering

Applications, Case Studies and Exercises

Apply Fast Integer & Modular Arithmetic

Next in the Series

Continue the Series

Polynomial Algorithms, FFT & NTT