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.
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/.