Finite Fields, Polynomial Arithmetic, and an Implementer's View of NTT TODO
Concept
A finite field is an algebraic structure with finitely many elements where addition, multiplication, and division by anything nonzero are all defined; cryptography and ZK mostly work over a prime field F_p for some large prime p. Polynomial multiplication over this field is O(n^2) by definition, but if you choose p so that its multiplicative group contains a subgroup of size a power of two — that is, a root of unity of suitable order — you can perform an FFT-like transform over the integers with zero error, and that's the NTT. Because NTT has no floating-point rounding error and its results land exactly on field elements, it suits proof systems; multiplication turns into an elementwise product in the evaluation domain, bringing the whole operation to O(n log n). In implementation, the key optimizations are cutting modular-multiplication cost with Montgomery or Barrett reduction, and applying lazy reduction inside the butterfly operations to reduce the number of modulo operations.
A large share of ZK proof-generation time comes from NTT and polynomial arithmetic, so estimating or tuning proving cost requires understanding this layer.
Code & Formula
# 유한체·다항식 산술과 NTT — 소수체 F_p 위에서 단위근을 이용한 NTT로 다항식 곱셈을
# O(n log n) 에 수행하고, 결과가 나이브 O(n^2) 합성곱과 정확히 일치함을 검증한다 (교육용).
MOD = 998244353 # NTT 친화 소수: MOD - 1 이 2의 큰 거듭제곱을 인수로 가짐
ROOT = 3 # MOD 의 원시근
def ntt(a, invert):
n = len(a)
j = 0
for i in range(1, n): # bit-reversal permutation
bit = n >> 1
while j & bit:
j ^= bit
bit >>= 1
j ^= bit
if i < j:
a[i], a[j] = a[j], a[i]
length = 2
while length <= n:
w = pow(ROOT, (MOD - 1) // length, MOD)
if invert:
w = pow(w, MOD - 2, MOD) # 페르마 소정리로 역원 계산
for i in range(0, n, length):
wn = 1
for k in range(length // 2):
u = a[i + k]
v = a[i + k + length // 2] * wn % MOD
a[i + k] = (u + v) % MOD
a[i + k + length // 2] = (u - v) % MOD
wn = wn * w % MOD
length <<= 1
if invert:
n_inv = pow(n, MOD - 2, MOD)
for i in range(n):
a[i] = a[i] * n_inv % MOD
return a
def poly_multiply_ntt(a, b):
n = 1
while n < len(a) + len(b):
n <<= 1
fa = a + [0] * (n - len(a))
fb = b + [0] * (n - len(b))
ntt(fa, False)
ntt(fb, False)
fc = [(x * y) % MOD for x, y in zip(fa, fb)]
return ntt(fc, True)[: len(a) + len(b) - 1]
def poly_multiply_naive(a, b):
result = [0] * (len(a) + len(b) - 1)
for i, x in enumerate(a):
for j, y in enumerate(b):
result[i + j] = (result[i + j] + x * y) % MOD
return result
poly_a = [1, 2, 3, 4] # 1 + 2x + 3x^2 + 4x^3
poly_b = [5, 6, 7] # 5 + 6x + 7x^2
ntt_result = poly_multiply_ntt(poly_a[:], poly_b[:])
naive_result = poly_multiply_naive(poly_a, poly_b)
print("F_p with p =", MOD, "| primitive root =", ROOT)
print("NTT-based product: ", ntt_result)
print("naive O(n^2) product:", naive_result)
print("NTT matches naive convolution exactly:", ntt_result == naive_result)
docs/code/algorithms/algorithms-90.py
Exercise
Pick a prime suited for NTT, implement forward and inverse NTT over F_p directly, and cross-check polynomial multiplication results against naive O(n^2) multiplication using random inputs.
Practical Connection
When evaluating a rollup or ZK-based verification adoption, proving time and cost estimates ultimately come from circuit size and the NTT cost that scales with it, and that, together with on-chain verification gas, drives the architecture choice.
Where it lands in Jayverse
- Devnet: since a later OP-Stack L2 is the target chain, price any validity-proof rollup option's NTT cost against on-chain verification gas before choosing it over an optimistic design.
- Auditor: record which prime field and reduction technique (Montgomery or Barrett) any ZK-related pinned dependency uses, since that choice sets the proving-cost numbers the team ends up quoting.
- Number: if Number ever publishes a proving-cost or ZK-adoption estimate as an indicator, tie the number to concrete circuit size and NTT cost rather than a vendor claim.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| an implementer's view | 구현자 관점에서 본 · "an Implementer's View of NTT" |
| land on | 정확히 ~에 맞아떨어지다 · "results land exactly on field elements" |
| suit | ~에 적합하다 · "that's why it suits proof systems" |
| elementwise | 원소별로, 성분별로 · "an elementwise product in the evaluation domain" |
| cut cost | 비용을 줄이다 · "cutting modular-multiplication cost" |
| tune | (성능을) 조정하다, 맞추다 · "estimating or tuning proving cost" |
| NTT | 수론적 변환(Number Theoretic Transform) · 유한체 위에서 오차 없이 수행하는 FFT류 다항식 곱셈 변환, ZK 증명 생성의 핵심 연산. "bringing the whole operation to O(n log n)" |
| FFT | 고속 푸리에 변환(Fast Fourier Transform) · 다항식 곱셈을 빠르게 하는 변환, NTT는 이를 정수 위에서 오차 없이 구현한 버전. "an FFT-like transform over the integers with zero error" |
| Montgomery reduction | 몽고메리 리덕션(Montgomery reduction) · 모듈러 곱셈 비용을 줄이는 구현 최적화 기법. "cutting modular-multiplication cost with Montgomery or Barrett reduction" |
| Barrett reduction | 바렛 리덕션(Barrett reduction) · 모듈로 연산 비용을 줄이는 구현 최적화 기법. "Montgomery or Barrett reduction, and applying lazy reduction" |
| ZK | 영지식(Zero-Knowledge) · 증명 시스템을 가리키는 맥락, 대부분 소수체 F_p 위에서 연산. "cryptography and ZK mostly work over a prime field" |
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/.