18.23 Complexity Analysis

Number theory algorithms often look fast because their code is short. That can be misleading. A loop that runs log n times may still be expensive if each iteration multiplies thousand-bit integers. A primality test may look constant-time for machine integers but behave very differently for arbitrary-precision inputs.

This section collects the complexity models used throughout the chapter and shows how to reason about number-theoretic algorithms in practice.

Problem

Given a number-theoretic algorithm, estimate its running time and memory use accurately enough to choose the right implementation.

Examples:

gcd(a,b)

a^b mod m

is_prime(n)

factorize(n)

sieve(n)

The key is knowing whether the analysis counts arithmetic operations or bit operations.

Arithmetic Operation Model

In many algorithm discussions, we assume basic arithmetic operations are constant-time:

addition
multiplication
division
modulo
comparison

This model is reasonable when all values fit in machine words, such as 32-bit or 64-bit integers.

Under this model:

gcd(a,b)          → O(log min(a,b))
mod_pow(a,b,m)   → O(log b)
trial division   → O(√n)
sieve            → O(n log log n)

This model is simple and useful for ordinary programming problems.

Bit Complexity Model

For large integers, arithmetic operations are not constant-time.

Let:

L = number of bits in n

Then:

n ≈ 2^L

A number with one million bits requires much more work than a 64-bit integer.

Under a simple bit model:

Operation	Classical Cost
Addition	O(L)
Comparison	O(L)
Multiplication	O(L²)
Division	O(L²)
Modulo	O(L²)
GCD	implementation-dependent

Modern big integer libraries use faster multiplication algorithms for large inputs, but O(L²) is a useful conservative model.

Input Size Matters

For number theory, the numeric value n and the input length L are very different.

If:

L = log₂ n

then:

√n = 2^(L/2)

So an algorithm with complexity:

O(√n)

is exponential in the input length.

This distinction explains why trial division is poor for large integers.

Example:

n has 1024 bits

Then:

√n has about 512 bits

Trying all divisors up to √n is completely infeasible.

Euclidean Algorithm

The Euclidean Algorithm repeatedly replaces:

(a,b)

with:

(b, a mod b)

The number of iterations is:

O(log min(a,b))

In the arithmetic model, this is the full complexity.

In the bit model, each modulo operation has cost depending on the number of bits, so the total cost is higher. In practice, standard library GCD implementations are heavily optimized and should be preferred.

Use:

from math import gcd

rather than implementing your own unless the implementation is part of the exercise.

Extended Euclidean Algorithm

Extended Euclid performs the same number of divisions as Euclid and also updates coefficients.

Arithmetic model:

O(log min(a,b))

Space:

O(1)

for the iterative version.

The coefficient values can grow, but they remain bounded by the input scale. In big integer settings, the cost is similar to GCD plus additional multiplications and subtractions.

Modular Exponentiation

Binary exponentiation performs one loop per bit of the exponent.

Arithmetic model:

O(log exponent)

Each iteration performs one or two modular multiplications.

If values are big integers, the cost becomes:

O(log exponent × M(L))

where M(L) is the cost of multiplying L-bit integers.

In Python, prefer:

pow(base, exponent, modulus)

It uses optimized modular exponentiation.

Modular Inverse

There are two common methods.

Extended Euclid:

O(log m)

Fermat inverse under prime modulus:

a^(m-2) mod m

using modular exponentiation:

O(log m)

Both are logarithmic in the arithmetic model.

In practice:

Extended Euclid

is usually faster for a single inverse because it avoids exponentiation.

Fermat's method is convenient when working under a known prime modulus and an optimized pow is available.

Trial Division

Trial division tests divisors up to:

√n

Arithmetic model:

O(√n)

This is fine for small n, but exponential in the bit length of n.

A common mistake is assuming O(√n) is efficient because it looks sublinear. It is not efficient for large encoded integers.

Use trial division when:

n is small

or when:

you only need to remove small factors

Do not use it as the main factorization method for large inputs.

Sieve of Eratosthenes

The classic sieve computes primes up to n.

Time:

O(n log log n)

Space:

O(n)

This is excellent when n is moderate and many primes or primality queries are needed.

The memory cost is often the limiting factor.

For very large intervals, use a segmented sieve:

Time:  O(n log log n) over the range
Space: O(√R + block_size)

where R is the upper endpoint.

Smallest Prime Factor Sieve

An SPF sieve precomputes smallest prime factors for all values up to n.

Preprocessing:

O(n log log n)

or:

O(n)

with a linear sieve.

Factorization query:

O(number of prime factors with multiplicity)

This is usually:

O(log n)

because every division removes at least a factor of 2.

Use SPF when the query count is high.

Miller-Rabin

Each Miller-Rabin round performs modular exponentiation.

Arithmetic model:

O(k log n)

modular multiplications for k bases.

Bit model with classical multiplication:

O(k log³ n)

as a useful rough estimate.

For 64-bit integers, deterministic Miller-Rabin with fixed bases is extremely fast. For arbitrary-size integers, the number of rounds and multiplication cost both matter.

Pollard's Rho

Pollard's Rho has expected time roughly:

O(√p)

where p is the smallest nontrivial factor of n.

This is much better than:

O(√n)

when n has a small or medium-sized factor.

However, for a product of two similarly sized large primes, Pollard's Rho is still expensive.

This matters for RSA-like semiprimes, where both factors are intentionally large.

Chinese Remainder Theorem

For k congruences, the direct construction computes a product and k modular inverses.

Arithmetic model:

O(k log M)

roughly, where:

M = m₁m₂...mₖ

Incremental CRT is often easier to implement and can reduce intermediate handling.

Memory:

O(1)

besides big integer storage.

The product M can grow quickly, so bit complexity matters.

Möbius and Phi Sieves

Computing all phi values up to n:

O(n log log n)

with a standard sieve.

Computing all Möbius values with a linear sieve:

O(n)

Space:

O(n)

These are batch algorithms. They pay a preprocessing cost to make later queries cheap.

Modular Combinatorics

Factorial and inverse factorial preprocessing:

O(n)

Memory:

O(n)

Combination query:

O(1)

Lucas theorem:

O(log_p n)

queries after precomputing factorials up to p-1.

The right method depends heavily on:

maximum n
number of queries
modulus size
whether the modulus is prime

Discrete Logarithms

Brute force:

O(p)

Baby-Step Giant-Step:

O(√p)

time and:

O(√p)

memory.

Pollard's Rho for logarithms:

O(√p)

expected time and:

O(1)

memory.

Discrete logarithms remain hard for large cryptographic groups.

Complexity Comparison Table

Task	Common Algorithm	Time	Space
GCD	Euclid	O(log n)	O(1)
Modular inverse	Extended Euclid	O(log n)	O(1)
Modular power	Binary exponentiation	O(log e)	O(1)
Prime list up to n	Sieve	O(n log log n)	O(n)
Single primality test	Miller-Rabin	O(k log³ n) bit model	O(1)
Small factorization	Trial division	O(√n)	O(1)
Large factorization	Pollard's Rho	expected O(√p)	O(1)
Many factorizations ≤ n	SPF sieve	preprocess O(n) or O(n log log n)	O(n)
Combination query	factorial tables	O(1) after O(n) preprocessing	O(n)
Discrete log	BSGS	O(√p)	O(√p)

Choosing by Constraints

Use constraints to select the algorithm.

If:

n ≤ 10^6

trial division and simple sieves are often enough.

If:

n ≤ 10^7 or 10^8

a sieve may work, depending on memory.

If:

n fits in 64 bits

Miller-Rabin plus Pollard's Rho is usually practical.

If:

n has hundreds or thousands of bits

use mature big integer and cryptographic libraries. Do not rely on textbook implementations.

Query Count Changes Everything

A one-time computation and a million queries need different solutions.

Example:

factorize one number ≤ 10^9

Trial division may be fine.

But:

factorize one million numbers ≤ 10^7

requires an SPF table.

Similarly:

one C(n,k) query

may use direct multiplication.

But:

one million C(n,k) queries

requires factorial precomputation.

Memory Trade-Offs

Many number theory algorithms trade memory for speed.

Examples:

sieve table
SPF table
factorial table
inverse factorial table
baby-step table
log table

Before allocating, estimate memory.

A Python list of integers is much larger than a raw C array. For large tables, use arrays, bytearrays, or specialized numeric storage when needed.

Common Mistakes

Confusing n with log n

For integer inputs, the input size is roughly log n, not n.

Treating Big Integer Operations as Constant-Time

They are not. Multiplication, division, and modulo become expensive.

Ignoring Query Count

Preprocessing only makes sense when reused.

Underestimating Memory

An O(n) table may be too large in Python even when it seems acceptable on paper.

Choosing Cryptographic Algorithms from Textbook Complexity Alone

Security depends on parameter sizes, implementation details, randomness, and side-channel resistance, not only asymptotic complexity.

Testing Performance

Use small benchmarks to validate assumptions.

from time import perf_counter

def time_call(fn, *args):
    start = perf_counter()
    result = fn(*args)
    elapsed = perf_counter() - start
    return result, elapsed

Example:

_, elapsed = time_call(pow, 7, 10**7, 1_000_000_007)
print(elapsed)

For preprocessing methods, measure both:

build time
query time

A method with high preprocessing cost may be poor for a small number of queries.

Takeaway

Complexity analysis in number theory requires two lenses. For machine integers, arithmetic operations can often be treated as constant-time, giving familiar bounds such as O(log n), O(√n), and O(n log log n). For big integers, the input size is the number of bits, and multiplication, division, modulo, and exponentiation carry real costs. Good algorithm selection depends on value size, bit length, query count, memory budget, and whether results must be exact, probabilistic, or cryptographically safe.