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.
Where it lands in Jayverse
- Verex/Auditor: choose Montgomery vs. Barrett by the actual access pattern. If Verex ever adds a ZK-based resolution or privacy feature, benchmark both against the specific modulus used — Montgomery for repeated multiplications under one modulus, Barrett for one-off reductions — rather than defaulting to one.
- Auditor: add constant-time verification to the review checklist. Any custom elliptic-curve or modular-exponentiation code that bypasses the standard EVM precompiles must be checked for branching on secret values, since timing leaks are the risk the card names explicitly.
- DeFi: prefer the standard precompiles over hand-rolled bignum math. Where DeFi's algorithms need modular exponentiation, route through Ethereum's priced precompiles rather than a custom implementation, since their gas pricing already reflects this layer's real cost.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| pays off | 이득이 되다·보람이 있다 · 특정 조건에서 어떤 선택이 결국 이익으로 돌아올 때. "it pays off when you do many multiplications" |
| in a row | 연이어·연속으로 · 같은 연산을 여러 번 잇달아 수행하는 상황을 말할 때. "many multiplications under the same modulus in a row" |
| leak | (정보가) 새어나가다 · 타이밍 차이로 비밀값이 노출될 위험을 가리킬 때. "can leak secret values" |
| constant-time | 입력값과 무관하게 일정한 시간이 걸리는 · 타이밍 공격을 막기 위한 구현 방식. "constant-time implementations are required" |
| one-off | 한 번뿐인·일회성의 · 반복 없이 딱 한 번만 수행하는 연산에 적합할 때. "it suits one-off reductions" |
| throughput | 처리량 · 단위 시간당 처리할 수 있는 연산의 양을 가리키는 성능 지표. "directly decides throughput and gas cost" |
| precompute | 미리 계산해 두다 · 실행 전에 값을 구해놓아 나중 연산을 빠르게 하는 기법. "Barrett reduction precomputes an approximation" |
| TAOCP | 도널드 크누스의 저서(The Art of Computer Programming) · 몽고메리·바렛 리덕션 등 이 카드가 참고하는 알고리즘 고전 교과서. "Montgomery and Barrett Reduction (TAOCP Vol. 2)" |
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/.