Multi-Precision Arithmetic (Bignum) — Montgomery and Barrett Reduction (TAOCP Vol. 2), the Real Bottleneck in EC/ZK Implementations TODO
Concept
Multi-precision arithmetic represents integers larger than a machine word as an array of words and operates on them; in cryptographic implementations, the most expensive operation is modular multiplication. Division is far slower than multiplication, so avoiding actual division in modular reduction is the key optimization. Montgomery reduction picks a power of two R coprime with the modulus, moves numbers into Montgomery representation, and then performs reduction using only multiplications and shifts to effectively multiply by R's inverse. Because the representation conversion itself has a cost, it pays off when you do many multiplications under the same modulus in a row, as in modular exponentiation. Barrett reduction precomputes an approximation of the modulus's reciprocal and replaces division with multiplication and shifts; it has no representation conversion, so it suits one-off reductions. Either way, timing differences from conditional branches can leak secret values, so constant-time implementations are required.
A large share of the time spent verifying an elliptic-curve signature or generating a ZK proof goes into field multiplication, so the representation and reduction choice at this layer directly decides throughput and gas cost.
Code & Formula
# 다중정밀 산술(bignum) — Barrett 리덕션을 직접 구현해 나눗셈 없이 모듈러 축약을 하고,
# 파이썬 내장 % 연산과 결과가 일치하는지 검증한다 (Montgomery와 대비되는 단발성 리덕션 기법).
def barrett_precompute(modulus, k):
"""mu = floor(4^k / modulus) 를 미리 계산 — 이후 리덕션에서 나눗셈 대신 시프트+곱셈만 쓴다."""
return (1 << (2 * k)) // modulus
def barrett_reduce(x, modulus, k, mu):
"""x < modulus^2 가정. 나눗셈 없이 근사 몫을 구하고 보정한다."""
q_hat = (x * mu) >> (2 * k)
r = x - q_hat * modulus
while r >= modulus: # 근사 오차 보정 (최대 2번이면 충분함이 알려져 있다)
r -= modulus
while r < 0:
r += modulus
return r
MODULUS = (1 << 61) - 1 # 토이 소수 모듈러스 (61비트)
K = MODULUS.bit_length()
MU = barrett_precompute(MODULUS, K)
import random
random.seed(7)
mismatches = 0
for _ in range(2000):
a = random.getrandbits(60)
b = random.getrandbits(60)
product = a * b # 모듈러 곱셈에서 실제로 리덕션이 필요한 값
expected = product % MODULUS # 파이썬 내장 나눗셈 기반 리덕션
got = barrett_reduce(product, MODULUS, K, MU)
if got != expected:
mismatches += 1
print("modulus:", MODULUS, "| k (bit length):", K)
print("precomputed mu = floor(4^k / modulus):", MU)
print("random trials:", 2000, "| mismatches vs builtin %:", mismatches)
print("Barrett reduction matches builtin modulo:", mismatches == 0)
print("note: Montgomery reduction instead converts to a special representation")
print(" once and amortizes it over many multiplications (e.g. modexp loops).")
docs/code/algorithms/algorithms-88.py
Exercise
Implement modular multiplication over a prime modulus using 64-bit word arrays, once with naive division and once with Montgomery reduction, then compare their runtime performing the same modular exponentiation.
Practical Connection
This layer's cost structure is exactly why Ethereum's pairing and modular-exponentiation precompiles exist, why they're priced the way they are, and where an off-chain proof generator's bottleneck actually sits.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.