Capstok — learn by doing

Why this matters

Polynomials are the central object of every modern ZK proof system. SNARKs (PLONK, Marlin), STARKs, and IOPs all reduce a computational claim to a statement about a low-degree polynomial $P$ over $\mathbb{F}_p$ — 'I know $P$ that satisfies these constraints' — and then prove it by querying $P$ at random points. The reason polynomials work where matrices and arrays don't: a degree- $d$ polynomial over a field is determined by $d+1$ evaluations and differs from any other polynomial of degree $d$ at all but at most $d$ points. That tiny algebraic fact (which we'll prove next task as Schwartz–Zippel) is the engine that lets a verifier check a long computation in a few field operations. Master this representation now.

Demo

$\mathbb{F}_p[X]$ is the ring of polynomials with coefficients in $\mathbb{F}_p$ . Addition and multiplication are coefficient-wise / convolutional, both reduced mod $p$ . Two distinct polynomials of degree at most $d$ agree on at most points.

P(X) = \sum_{i=0}^{d} a_i X^i,\ a_i \in \mathbb{F}_p. \quad P, Q \in \mathbb{F}_p[X],\ \deg(P), \deg(Q) \leq d,\ P \neq Q \implies |\{x : P(x) = Q(x)\}| \leq d.

Try it yourself

Run the snippet. Confirm $(X+1)(X+2) = X^2 + 3X + 2$ in $\mathbb{F}_{17}$ , and that .

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, explain what a polynomial over a finite field is and how it differs from a polynomial over $\mathbb{R}$. Why do we care about coefficient-wise reduction mod $p$?

2. Why it works (the mechanism)

Walk me through Horner's rule for polynomial evaluation and why it costs only $d$ multiplications and $d$ additions for a degree-$d$ polynomial. Why does this matter for verifier efficiency in a SNARK?

3. Advanced — application & what's next

SNARKs pick fields with high *two-adicity* (large $2^k \mid p-1$) so they can use the FFT for polynomial multiplication in $O(n \log n)$ rather than $O(n^2)$. Sketch why this matters when the prover has to multiply polynomials of degree $\sim 10^6$, and what the prover has to do if the field has low two-adicity.

References

// main.go
package main

import "fmt"

// Polynomial arithmetic over F_p, coefficients low-degree-first.
const p = 17

func padd(A, B []int) []int {
	n := len(A)
	if len(B) > n {
		n = len(B)
	}
	C := make([]int, n)
	for i := 0; i < n; i++ {
		a, b := 0, 0
		if i < len(A) {
			a = A[i]
		}
		if i < len(B) {
			b = B[i]
		}
		C[i] = (a + b) % p
	}
	return C
}

func pmul(A, B []int) []int {
	C := make([]int, len(A)+len(B)-1)
	for i, a := range A {
		for j, b := range B {
			C[i+j] = (C[i+j] + a*b) % p
		}
	}
	return C
}

func peval(A []int, x int) int {
	acc := 0
	for k := len(A) - 1; k >= 0; k-- { // Horner's rule
		acc = (acc*x + A[k]) % p
	}
	return acc
}

func main() {
	// P(X) = X^2 + 3X + 2 = (X+1)(X+2) over F_17
	P := []int{2, 3, 1}
	Q := pmul([]int{1, 1}, []int{2, 1}) // (X+1)(X+2)
	fmt.Printf("P = %v  Q = %v  equal? %v\n", P, Q, fmt.Sprint(P) == fmt.Sprint(Q))
	vals := make([]int, 5)
	for x := 0; x < 5; x++ {
		vals[x] = peval(P, x)
	}
	fmt.Println("P(0)..P(4):", vals)
}

Run: go run main.go

Polynomial arithmetic over finite fields