18.21 Big Integer Concerns

Number-theoretic algorithms often look simple when written with mathematical notation. In code, the details are less forgiving. Modular multiplication can overflow. Exponentiation can allocate huge temporary values. Division may dominate runtime. Randomized algorithms may behave differently across platforms. Cryptographic code may leak information through timing.

Big integer concerns are the implementation layer beneath computational number theory. They determine whether an otherwise correct algorithm remains correct, fast, and safe when inputs grow beyond native machine words.

Problem

Given arithmetic algorithms involving large integers, implement operations such as:

a + b
a × b
a^e mod m
gcd(a,b)
a⁻¹ mod m

without overflow, excessive memory use, accidental precision loss, or avoidable performance problems.

The challenge is that mathematical integers are unbounded, while machine integers usually are not.

Fixed-Width Integers

Most systems provide fixed-width integer types.

Common examples:

Type	Approximate Range
32-bit unsigned	0 to 2³² - 1
64-bit unsigned	0 to 2⁶⁴ - 1
signed 64-bit	-2⁶³ to 2⁶³ - 1

If a result exceeds the range, behavior depends on the language.

In Python, integers grow automatically. In C and C++, signed overflow is undefined behavior. In Go, Rust, Java, and many other languages, fixed-width integer operations wrap, panic in checked modes, or require explicit big integer types.

This matters because modular arithmetic commonly contains expressions such as:

(a × b) mod m

Even if the final residue fits in 64 bits, the product a × b may not.

Overflow Before Modulo

Consider:

a = 10^18
b = 10^18
m = 10^18 + 7

The final answer:

(a × b) mod m

is less than m, so it fits in 64 bits.

But the intermediate product:

a × b = 10^36

does not fit in 64 bits.

This is a classic source of incorrect modular arithmetic in fixed-width languages.

Safe Modular Multiplication

In Python, this is safe:

def mod_mul(a, b, m):
    return (a * b) % m

In a fixed-width language, use one of these strategies:

wider intermediate type
big integer library
Montgomery multiplication
Barrett reduction
repeated-doubling multiplication

For example, in C++ with 64-bit values, __int128 is commonly used for the intermediate product.

Conceptually:

result = ((128-bit)a × b) mod m

This handles moduli up to 64 bits.

Repeated-Doubling Multiplication

When no wider type exists, multiplication can be simulated through addition and doubling.

def mod_mul_slow(a, b, m):
    a %= m
    b %= m
    result = 0

    while b > 0:
        if b & 1:
            result = (result + a) % m

        a = (a + a) % m
        b >>= 1

    return result

Complexity:

O(log b)

This is slower than native multiplication, but avoids overflow.

Use it when correctness matters and no better primitive is available.

Modular Exponentiation with Safe Multiplication

Fast exponentiation depends on multiplication.

def mod_pow_safe(base, exponent, modulus):
    result = 1
    base %= modulus

    while exponent > 0:
        if exponent & 1:
            result = mod_mul_slow(result, base, modulus)

        base = mod_mul_slow(base, base, modulus)
        exponent >>= 1

    return result

This version is safe for fixed-width-style arithmetic but slower than normal multiplication.

In Python, prefer built-in pow(base, exponent, modulus).

Prefer Built-In Big Integer Operations

In Python, this is usually the best implementation:

pow(base, exponent, modulus)

It is faster and more memory-efficient than:

(base ** exponent) % modulus

because it performs modular reduction throughout exponentiation.

Use:

pow(a, -1, m)

for modular inverse when available.

Example:

print(pow(3, -1, 11))

Output:

4

This computes the inverse of 3 modulo 11.

Avoid Floating-Point Arithmetic

Number theory should usually remain integer-only.

Avoid:

int(n ** 0.5)

for large n.

Floating-point square roots can round incorrectly.

Use:

from math import isqrt

limit = isqrt(n)

This returns the exact integer floor of the square root.

Example:

from math import isqrt

def is_square(n):
    r = isqrt(n)
    return r * r == n

This is exact for arbitrarily large integers.

Big Integer Cost Model

For native integers, we often treat arithmetic as constant time.

For big integers, arithmetic cost depends on the number of machine words.

Let:

L = number of bits in n

Then common operations have approximate costs:

Operation	Rough Cost
Addition	O(L)
Comparison	O(L)
Multiplication, classical	O(L²)
Division	O(L²)
GCD	O(L² log L), implementation-dependent
Modular exponentiation	O(log e) multiplications

Real big integer libraries use faster algorithms for large inputs, but the key point remains: arithmetic itself is no longer free.

This affects algorithm selection.

Memory Allocation

Big integer operations allocate temporary objects.

The expression:

x = (a * b + c * d) % m

may allocate intermediate products before reduction.

When performance matters, reduce aggressively:

x = (a * b) % m
x = (x + (c * d) % m) % m

In Python, this still allocates, but it keeps values smaller. In lower-level languages, specialized modular arithmetic routines can avoid repeated allocation.

Sign Handling

Big integer libraries may represent negative values differently internally, but APIs generally preserve mathematical semantics.

Still, modular arithmetic with negative numbers should be normalized.

def normalize_mod(x, m):
    return x % m

In Python:

-3 % 5 == 2

In some languages, the remainder may keep the sign of the dividend.

A portable normalization pattern is:

((x % m) + m) % m

Use this when porting algorithms across languages.

GCD and Extended GCD

GCD is usually highly optimized in standard libraries.

In Python:

from math import gcd

print(gcd(123456789, 987654321))

For modular inverses, Extended Euclid remains useful:

def extended_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1

    while r:
        q = old_r // r

        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t

    return old_r, old_s, old_t

For production code, prefer library primitives when available.

Random Big Integers

Randomized algorithms such as Miller-Rabin and Pollard's Rho require random bases or starting values.

For non-cryptographic algorithms:

import random

may be enough.

For cryptographic code, use a cryptographically secure generator:

import secrets

x = secrets.randbelow(n)

Do not use ordinary pseudorandom generators for key generation, primality generation, or security-sensitive randomness.

Timing Side Channels

In cryptographic code, the execution time of arithmetic operations may reveal information about secret values.

Examples:

branching on secret bits
variable-time modular exponentiation
early exits based on secret data
table lookups indexed by secrets

The textbook fast exponentiation loop:

if exponent & 1:
    result = result * base % modulus

branches on exponent bits. That is acceptable for ordinary algorithms but problematic when the exponent is secret.

Cryptographic libraries use constant-time algorithms or blinding techniques.

Do not implement cryptographic primitives from scratch unless you understand these constraints.

Big Integer Libraries

Different languages provide different big integer support.

Language	Common Big Integer Support
Python	built-in int
Java	BigInteger
Go	math/big
Rust	num-bigint, crypto-specific crates
C++	Boost.Multiprecision, GMP
C	GMP, OpenSSL BIGNUM
JavaScript	BigInt

For serious performance, mature libraries such as GMP are often much faster than simple language-level implementations.

Performance Pattern: Reduce Early

When computing expressions modulo m, reduce after each operation.

Prefer:

x = (a % m) * (b % m) % m

over:

x = (a * b) % m

when a and b may already be huge.

For Python this is mostly a performance issue. In fixed-width languages it may also be a correctness issue.

Performance Pattern: Batch Precomputation

If an algorithm repeatedly needs modular inverses, factorials, powers, or prime tables, precompute once.

Examples:

factorial table
inverse factorial table
smallest prime factor table
powers of a generator
Montgomery constants

Precomputation trades memory for speed and often turns repeated logarithmic operations into constant-time lookups.

Performance Pattern: Choose the Right Modulus

Some moduli are friendlier than others.

Prime moduli simplify inverse computations.

NTT-friendly primes support fast polynomial multiplication.

Powers of two enable bit masking:

x mod 2^k

can be computed as:

x & (2^k - 1)

provided x is nonnegative and the language's integer model is compatible.

Cryptographic moduli are selected according to stricter security and algebraic requirements.

Common Mistakes

Computing Huge Powers Directly

Avoid:

(base ** exponent) % modulus

when exponent is large.

Use:

pow(base, exponent, modulus)

Assuming Multiplication Cannot Overflow

Even if the final result is reduced modulo m, the intermediate product can overflow.

Using Floating-Point Square Roots

Use isqrt, not floating-point approximation.

Using Non-Crypto Randomness for Crypto

Use secrets or a cryptographic library for key material.

Writing Crypto from Scratch

Number-theoretic code for learning is different from production cryptography.

Side-channel resistance, parameter validation, padding, randomness, and protocol design all matter.

Testing

For modular multiplication, compare safe and direct versions in Python:

def test_mod_mul_slow():
    cases = [
        (10**18, 10**18, 10**18 + 7),
        (2**63 - 1, 2**63 - 5, 2**61 - 1),
        (123456789, 987654321, 1000000007),
    ]

    for a, b, m in cases:
        assert mod_mul_slow(a, b, m) == (a * b) % m

For modular exponentiation:

def test_mod_pow_safe():
    for base in range(1, 100):
        for exponent in range(0, 100):
            for modulus in range(1, 50):
                assert mod_pow_safe(base, exponent, modulus) == pow(base, exponent, modulus)

For square roots:

from math import isqrt

def test_is_square():
    for n in range(10000):
        r = isqrt(n)
        assert (r * r == n) == is_square(n)

These tests are simple but catch the most common arithmetic errors.

Takeaway

Big integer concerns are where mathematical algorithms meet machine limits. Modular arithmetic must avoid overflow before reduction, exponentiation should use modular methods rather than full powers, square-root bounds should use exact integer arithmetic, and cryptographic code must consider randomness and timing behavior. Languages with built-in big integers remove many correctness hazards, but they do not remove performance costs. Reliable number-theoretic software depends on choosing the right arithmetic representation, reducing early, using library primitives where possible, and testing edge cases aggressively.