The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

9 Roots of unity and evaluation domains

This section constructs the evaluation domains on which polynomial proof systems of the kind underlying Halo 2 and Zcash Orchard encode computations, and the fast Fourier transform on them. Such a proof system records an n-step computation as a table over a finite field, one column per register and one row per step, and convinces a verifier that every row follows from its predecessor without the verifier replaying the computation: by Lagrange interpolation (5.30) each column is the value table on n fixed points of a polynomial of degree less than n, so conditions on the table become polynomial identities, checkable at a single random point by the Schwartz–Zippel lemma (5.45). The powers of a primitive n-th root of unity form a point set on which conditions on every row, shifts to the next row and the polynomials attached to the set are cheap to evaluate, and on which conversion between values and coefficients, and polynomial multiplication, cost far fewer than the n2 field operations of the schoolbook methods. Such a root exists in 𝔽q exactly when n∣q−1 (9.7); its powers form the evaluation domain H, whose vanishing polynomial is Xn−1 (9.13) and whose Lagrange basis has a closed form (9.22); evaluation on H is the number-theoretic transform, which turns polynomial multiplication into entrywise multiplication of value vectors (9.32); and the fast Fourier transform computes it in O(nlogn) operations (9.37).

Throughout, 𝔽 denotes a field. When 𝔽 is to be finite, the notation 𝔽q denotes the field with q elements (so q is a prime power, 6.10); when we intend a prime field specifically we write 𝔽p. The multiplicative group of nonzero elements is 𝔽×=𝔽∖{0} (Example 3.7). We reserve the letter n for the order of the domain constructed below, with n≥1.

9.1 Roots of unity

Definition 9.1 (Root of unity).

Let 𝔽 be a field and n∈ℕ>0. An element ω∈𝔽 is an n-th root of unity if ωn=1. We write

μn⁢(𝔽)={ω∈𝔽:ωn=1}

for the set of all n-th roots of unity in 𝔽.

Since 0n=0≠1, we have 0∉μn(𝔽); every n-th root of unity is therefore a unit, i.e. lies in 𝔽×.

Proposition 9.2.

The set μn(𝔽) is a finite subgroup of 𝔽× of order at most n.

Proof.

The identity 1 satisfies 1n=1, so 1∈μn(𝔽). If ω,ζ∈μn(𝔽), then (ω⁢ζ)n=ωnζn=1⋅1=1 because 𝔽× is abelian, so ωζ∈μn(𝔽); and (ω−1)n=(ωn)−1=1−1=1, so ω−1∈μn(𝔽). Hence μn(𝔽) is a subgroup of 𝔽× (3.14). For the order bound, every element of μn(𝔽) is a root of the polynomial Xn−1∈𝔽[X], which is nonzero of degree n and so has at most n roots in 𝔽 (5.18). Thus |μn(𝔽)|≤n. □

The bound |μn(𝔽)|≤n need not be attained; it is attained exactly when 𝔽 contains a primitive n-th root of unity.

Definition 9.3 (Primitive root of unity).

An element ω∈𝔽 is a primitive n-th root of unity if ωn=1 and ωk≠1 for every integer k with 1≤k<n. Equivalently, ω is a primitive n-th root of unity if its multiplicative order ord(ω) (3.11) equals n.

The order ord(ω) is the least positive integer d with ωd=1; it exists for any ω∈μn(𝔽) because n itself is such an exponent and the positive integers are well-ordered. The two formulations in 9.3 agree, since both state that n is the least positive exponent d with ωd=1.

Remark 9.4 (Primitive roots as roots of unity).

The group-theoretic term “generator of 𝔽q×” and the polynomial term “primitive (q−1)-th root of unity” name the same elements, as announced in 6.21: a primitive root of a finite field 𝔽q, that is, a generator of the cyclic group 𝔽q× in the sense of 6.20, is an element of multiplicative order q−1, which by 9.3 is precisely a primitive (q−1)-th root of unity.

Lemma 9.5 (Order divides exponent).

Let ω∈𝔽× have finite order d=ord(ω). Then for any integer m we have ωm=1 if and only if d∣m. In particular, ω is an n-th root of unity if and only if d∣n, and ω is a primitive n-th root of unity if and only if d=n.

Proof.

The first claim is 3.12(1), read in the abelian group 𝔽×: if d∣m, write m=dk, so ωm=(ωd)k=1; conversely, division with remainder m=qd+r, 0≤r<d, gives 1=ωm=ωr, and minimality of d forces r=0. The remaining clauses instantiate it: ωn=1⇔d∣n is the case m=n, and primitivity is the case d=n by 9.3. □

Proposition 9.6.

If ω∈𝔽 is a primitive n-th root of unity, then

μn⁢(𝔽)=⟨ω⟩={ 1,ω,ω2,…,ωn−1}

is a cyclic group of order exactly n, and these n powers are pairwise distinct.

Proof.

The powers 1,ω,…,ωn−1 are pairwise distinct: if ωi=ωj with 0≤i≤j≤n−1, then ωj−i=1 with 0≤j−i<n, so primitivity (9.5, with d=n) forces j−i=0. Thus ⟨ω⟩ has exactly n elements, all of which lie in μn(𝔽) since (ωk)n=(ωn)k=1. But |μn(𝔽)|≤n by 9.2, so the inclusion ⟨ω⟩⊆μn(𝔽) is an equality of n-element sets. □

Over the complex numbers a primitive n-th root of unity always exists, namely ω=e2⁢π⁢i/n; the n-th roots of unity are n equally spaced points on the unit circle, and the primitive ones lie at the angles 2πk/n with gcd(k,n)=1. Over a finite field, the case used in cryptography, one exists only for the n determined in the next subsection.

Refer to caption
Figure 3: The eight 8-th roots of unity in ℂ, equally spaced on the unit circle at angles 2πk/8, with ω=e2⁢π⁢i/8. The four primitive ones (k=1,3,5,7, exactly the k coprime to 8; marked in colour) each generate the whole cycle; the grey points ω0=1, ω2=i, ω4=−1, ω6=−i have orders 1,4,2,4 and generate proper subgroups. Over a finite field the cyclic group structure persists without the geometry of the circle.

9.2 Existence over finite fields: the condition n∣q−1

The multiplicative group 𝔽q× of a finite field is cyclic of order q−1 (6.18); the existence theorem for roots of unity rests on this fact.

Theorem 9.7 (Existence and count of primitive n-th roots of unity).

Let 𝔽q be a finite field and n∈ℕ>0 with gcd(n,q)=1 (automatic when n<p, where p=char𝔽q; equivalently, in characteristic p, exactly the condition p∤n). Then:

  1. 1.

    The field 𝔽q contains a primitive n-th root of unity if and only if n∣q−1.

  2. 2.

    When n∣q−1, the group μn(𝔽q) is cyclic of order exactly n, and the number of primitive n-th roots of unity in 𝔽q is φ(n), where φ is Euler’s totient function (2.26).

Proof.

Let g be a generator of 𝔽q×, which is cyclic of order q−1 by 6.18.

(⇒) Suppose ω is a primitive n-th root of unity in 𝔽q. Then ω∈𝔽q× has order n by 9.3, and by Lagrange’s theorem the order of an element divides the group order q−1 (Corollary 3.30). Hence n∣q−1.

(⇐) Suppose n∣q−1, say q−1=nm. Set ω=gm. Then ωn=gm⁢n=gq−1=1, so ω∈μn(𝔽q). Its order is

ord⁡(ω)=ord⁡(gm)=ord⁡(g)gcd⁡(m,ord⁡(g))=q−1gcd⁡(m,q−1)=q−1m=n,

using the order-of-a-power formula (Corollary 3.23) together with m∣q−1 (so gcd(m,q−1)=m). Thus ω is a primitive n-th root of unity, and by 9.6, μn(𝔽q)=⟨ω⟩ is cyclic of order exactly n.

Count. In the cyclic group μn(𝔽q)=⟨ω⟩ of order n, the element ωk has order n/gcd(k,n), again by Corollary 3.23. This equals n precisely when gcd(k,n)=1, and the number of k∈{0,1,…,n−1} with gcd(k,n)=1 is by definition φ(n) (2.26). Hence there are exactly φ(n) primitive n-th roots of unity.

(On the coprimality hypothesis. The condition gcd(n,q)=1 is what guarantees that Xn−1 is separable—gcd(Xn−1,nXn−1)=1 when n≠0 in 𝔽q—hence has n distinct roots in a splitting field over 𝔽q (5.40); that all n of them lie in 𝔽q itself is exactly the condition n∣q−1. If p=char𝔽q divided n, then Xn−1 would have repeated roots and μn(𝔽q) would be strictly smaller. But n∣q−1 already forces gcd(n,q)=1, since gcd(q−1,q)=1, so the hypothesis is subsumed.) □

Remark 9.8.

The proof shows that for a finite field the statement reduces to 𝔽q has a primitive n-th root of unity ⇔n∣q−1, with no separate coprimality condition, because n∣q−1 makes n coprime to q; the theorem states the condition gcd(n,q)=1 only to exhibit the role of the characteristic.

Example 9.9.

Take 𝔽q=𝔽p with p=7. Here q−1=6, and 3 is a generator of 𝔽7×: its successive powers are 3,2,6,4,5,1, all six nonzero residues (Example 6.22). For n=3∣6, set m=6/3=2 and ω=32=2. Since 21=2, 22=4 and 23=8≡1, the element ω=2 has order 3 and μ3(𝔽7)={1,2,4}. There are φ(3)=2 primitive cube roots of unity, namely 2 and 4. By contrast 4∤6, so 𝔽7 has no primitive 4-th root of unity: X4−1=(X2−1)(X2+1), and X2+1 is irreducible over 𝔽7 because it has no root there, −1 not being a square modulo 7.

Remark 9.10 (Two-adicity and FFT-friendly primes).

For the fast algorithms below, n should be a power of two, or at least smooth—a product of small primes, ideally with many factors of two. By 9.7, a primitive 2k-th root of unity exists exactly when 2k∣q−1. The largest k with 2k∣q−1 is called the two-adicity of the field. Designers choose primes p of high two-adicity, p−1=2k⋅c for large k, as scalar fields of proof systems so that large smooth evaluation domains exist. Both Pasta primes—those underlying the Pallas and Vesta curves of 10—satisfy 232∣p−1, with two-adicity exactly 32 (the primes are specified in §5.4.9.6, “Pallas and Vesta”, of the Zcash protocol specification), so each Pasta field contains primitive 2k-th roots of unity for every k≤32, hence power-of-two evaluation domains of every size up to 232; every construction of this section therefore applies over the fields used by Halo 2 and Orchard.

9.3 The evaluation domain H and its vanishing polynomial

Definition 9.11 (Evaluation domain).

Let 𝔽 be a field containing a primitive n-th root of unity ω. The evaluation domain of order n is the multiplicative subgroup

H=⟨ω⟩={ 1,ω,ω2,…,ωn−1}=μn⁢(𝔽)⊆𝔽×,

a cyclic group of order n by 9.6. We index its elements as ω0,ω1,…,ωn−1, and abbreviate ωi by hi when convenient. Both 𝔽 and ω remain fixed for the rest of the section.

Definition 9.12 (Vanishing polynomial).

The vanishing polynomial (or zerofier) of H is

ZH⁢(X)=∏h∈H(X−h)∈𝔽⁢[X].

On a generic n-point set the vanishing polynomial (5.33) is a product of n linear factors with no simpler form; on the group H it reduces to a binomial.

Theorem 9.13 (Closed form and factorisation of the vanishing polynomial).

With H=μn(𝔽) of order n generated by a primitive n-th root of unity ω,

ZH⁢(X)=Xn−1=∏i=0n−1(X−ωi).

Moreover ZH is separable: it has n distinct roots and gcd(ZH,Z′H)=1.

Proof.

Every h∈H satisfies hn=1, hence is a root of Xn−1. The n elements of H are distinct (9.6), so Xn−1 has n distinct roots, namely all of H, and factors as Xn−1=c∏h∈H(X−h) for some constant c∈𝔽× by iterating the factor theorem (5.36, with the degree leaving no room for further factors). Comparing leading coefficients—both Xn−1 and the product are monic—gives c=1, whence Xn−1=∏h∈H(X−h)=ZH(X).

For separability, the formal derivative is Z′H(X)=nXn−1 (5.37). The existence of the n distinct roots already forces char𝔽∤n: if char𝔽=ℓ divided n, say n=ℓm, the freshman’s dream (6.14) would give Xn−1=(Xm−1)ℓ, a polynomial with at most m<n distinct roots—a contradiction. Hence n≠0 in 𝔽, so nXn−1 is nonzero at every element of H, since each is nonzero. Thus it has no root in common with Xn−1, so gcd(ZH,Z′H)=1 and ZH is separable (5.40). □

The proof shows that char𝔽∤n, so that division by n is defined in 𝔽. By the theorem, a polynomial f vanishes on all of H if and only if Xn−1 divides it, and ZH is evaluated at any point by a single exponentiation Xn, not n multiplications.

Proposition 9.14 (Cosets and shifts).

Let γ∈𝔽× and let γH={γh:h∈H} be the corresponding coset (3.27). Then the polynomial vanishing on γH is

Zγ⁢H⁢(X)=∏h∈H(X−γ⁢h)=Xn−γn.

In particular, distinct cosets of H in 𝔽× have vanishing polynomials Xn−c for distinct constants c=γn, and the cosets of H partition 𝔽× (3.28) into translates of H, on each of which Xn is constant.

Proof.

Substitute Y=X/γ:

∏h∈H(X−γ⁢h)=γn⁢∏h∈H(Y−h)=γn⁢(Yn−1)=γn⁢((X/γ)n−1)=Xn−γn,

using 9.13 for the middle equality. The constant is c=γn, and

γ1⁢H=γ2⁢H⇔γ1/γ2∈H⇔(γ1/γ2)n=1⇔γ1n=γ2n,

so distinct cosets give distinct constants c. □

Lemma 9.15 (Finite geometric series).

Let 𝔽 be a field, ζ∈𝔽 with ζ≠1, and n≥1. Then

∑i=0n−1ζi=ζn−1ζ−1.
Proof.

Write S=1+ζ+ζ2+⋯+ζn−1. Multiplying by ζ raises the exponent of every term by one:

ζ⁢S=ζ+ζ2+⋯+ζn−1+ζn.

In the difference ζS−S, the terms ζ,ζ2,…,ζn−1 appear in both lines and cancel; only the two extreme terms remain:

(ζ−1)⁢S=ζ⁢S−S=ζn−1.

Since ζ≠1, the factor ζ−1 is invertible, and dividing by it yields the claim. □

Proposition 9.16 (Sum of roots of unity).

If n>1 then ∑i=0n−1ωi=0, and more generally for any integer k,

∑i=0n−1ωk⁢i={nif ⁢n∣k,0if ⁢n∤k.
Proof.

If n∣k, then ωk⁢i=(ωn)k⁢i/n=1 for each i, so the sum is n. If n∤k, set ζ=ωk≠1 (since ω has order n, we have ωk=1⇔n∣k by 9.5), and 9.15 gives

∑i=0n−1ζi=ζn−1ζ−1=(ωn)k−1ζ−1=1−1ζ−1=0,

the denominator being nonzero because ζ≠1. The first claim is the case k=1, valid for n>1 since then n∤1. □

Remark 9.17 (Vanishing by rotation invariance).

For n∤k the vanishing also follows without the geometric-series formula. The n terms of ∑iωk⁢i run through the subgroup ⟨ζ⟩ generated by ζ=ωk, each element appearing equally often; multiplying the sum by ζ permutes the terms cyclically, so the sum satisfies ζS=S, and (ζ−1)S=0 with ζ≠1 forces S=0. 3 shows the complex case, in which rotation permutes the equally spaced points.

Remark 9.18 (Why “orthogonality”).

Call two vectors in 𝔽n orthogonal when their standard inner product (8.21) vanishes. For each frequency k let vk=(1,ωk,ω2⁢k,…,ω(n−1)⁢k) be its vector of powers, and let v¯k=(1,ω−k,ω−2⁢k,…,ω−(n−1)⁢k) be the same construction with ω−1 in place of ω: the mirror of vk, which traverses the cycle in the opposite direction and takes the role of the complex conjugate in the classical setting (on the unit circle z¯=z−1). Then ⟨v¯k,vk′⟩=∑iωi⁢(k′−k), which 9.16 evaluates to 0 for k≠k′ and to n for k=k′: distinct frequency vectors are orthogonal, and each pairs with its own mirror to n. (Which factor carries the mirror is a convention: with the roles exchanged the exponent is k−k′, and the criterion n∣k′−k is symmetric; the order chosen matches the product V¯V computed in 9.29.) This is the finite-field counterpart of the orthogonality of the exponentials θ↦e2⁢π⁢i⁢k⁢θ in classical Fourier analysis, with the sum over the cycle in place of the integral over the circle. The proof of the inverse transform (9.29) rests on it, the vk being the columns of the transform matrix.

9.4 The Lagrange basis on H

Since H has exactly n points, values on H determine polynomials of degree less than n (5.20); the basis adapted to values on H is the Lagrange basis of §5.7.

Definition 9.19.

Let 𝔽[X]<n denote the 𝔽-vector space of polynomials of degree strictly less than n, together with the zero polynomial. It has the monomial basis {1,X,…,Xn−1} (8.14), so dim𝔽𝔽[X]<n=n (8.17).

Definition 9.20.

For each i∈{0,1,…,n−1}, the i-th Lagrange basis polynomial for H={ω0,…,ωn−1} is

Li⁢(X)=∏j=0j≠in−1X−ωjωi−ωj∈𝔽⁢[X]<n,

the basis polynomial ℓi of 5.30 for the nodes ω0,…,ωn−1.

Proposition 9.21 (Interpolation property).

The polynomials L0,…,Ln−1 satisfy the Kronecker-delta conditions

Li⁢(ωj)=δi⁢j={1i=j,0i≠j,

they form a basis of 𝔽[X]<n, and they give the unique interpolant: for any data (v0,…,vn−1)∈𝔽n, the polynomial

f⁢(X)=∑i=0n−1vi⁢Li⁢(X)

is the unique element of 𝔽[X]<n with f(ωi)=vi for all i.

Proof.

Each Li is well defined and of degree n−1 because the nodes ωj are distinct (9.6), so the denominators ωi−ωj with j≠i are nonzero. The delta conditions, the interpolation f(ωj)=vj, and the uniqueness are 5.30 (with (4)) applied to these nodes with d=n−1; uniqueness rests, as there, on the root count: two interpolants in 𝔽[X]<n differ by a polynomial of degree <n with n distinct roots, which is the zero polynomial (5.18). It remains to see that the Li form a basis of 𝔽[X]<n. They are linearly independent: if ∑iciLi=0, evaluation at ωj yields cj=0 for every j (8.11). Being n independent vectors in the n-dimensional space 𝔽[X]<n (9.19), they form a basis (8.17). □

The root-count step recurs and is called the root-count device: two polynomials of degree <n that agree on all n points of H are equal. It gives the uniqueness above, 9.24, and Example 9.25 below.

On a generic point set the Lagrange polynomials admit no closed form simpler than the defining product; on the group H they are expressed through the vanishing polynomial.

Theorem 9.22 (Closed form of the Lagrange basis on H).

For H=μn(𝔽) with primitive root ω, and for each i,

Li⁢(X)=ωin⋅Xn−1X−ωi=ωi⁢(Xn−1)n⁢(X−ωi).

In particular, dividing out one linear factor and scaling yields all n Lagrange polynomials from the single polynomial ZH(X)=Xn−1.

Proof.

Fix i. From 9.13, ZH(X)=∏j=0n−1(X−ωj), so

ZH⁢(X)X−ωi=∏j=0j≠in−1(X−ωj),

which is exactly the numerator of Li in 9.20. It remains to evaluate the denominator ∏j≠i(ωi−ωj). Writing ZH=(X−ωi)g with g=∏j≠i(X−ωj), the product rule (5.38) gives Z′H=g+(X−ωi)g′, so

Z′H⁢(ωi)=g⁢(ωi)=∏j=0j≠in−1(ωi−ωj)

—the derivative at a simple root equals the product of the differences to the other roots, the computation already made for simple roots in the proof of 5.40. Concretely Z′H(X)=nXn−1, so

Z′H⁢(ωi)=n⁢(ωi)n−1=n⁢ωi⁢n⁢ω−i=n⋅1⋅ω−i=nωi,

using ωi⁢n=(ωn)i=1. Therefore

Li⁢(X)=ZH⁢(X)/(X−ωi)Z′H⁢(ωi)=(Xn−1)/(X−ωi)n/ωi=ωi⁢(Xn−1)n⁢(X−ωi),

as claimed. □

Remark 9.23 (Barycentric form).

The closed form gives the barycentric interpolation formula on H a compact form. Writing f(X)=∑iviLi(X) and substituting 9.22,

f⁢(X)=Xn−1n⁢∑i=0n−1ωi⁢viX−ωi.

Evaluating f at a point z∉H thus costs one evaluation of zn−1 and n terms of the sum, with no per-point polynomial reconstruction. A verifier can use this formula when the values vi are known, as for public-input polynomials; a commitment to hidden values does not by itself permit this evaluation.

Proposition 9.24 (Lagrange polynomials sum to one).

The Lagrange basis polynomials for H satisfy ∑i=0n−1Li(X)=1 identically.

Proof.

The polynomial g(X)=∑iLi(X)−1 lies in 𝔽[X]<n and vanishes at every ωj, because ∑iLi(ωj)=∑iδi⁢j=1 (9.21). By the root-count device—a polynomial of degree <n with n distinct roots is zero (5.18)—g≡0. □

Example 9.25 (The all-ones value vector).

The constant polynomial 1 interpolates the data vi=1 for all i; 9.24 is the statement ∑i1⋅Li=1. Likewise the values of X on H are vi=ωi, and, for n≥2, 9.21 gives ∑iωiLi(X)=X: both sides have degree <n and agree on all of H, so the root-count device applies. These identities are used to rewrite monomials in the Lagrange basis.

9.5 Evaluation and interpolation as mutually inverse linear maps

An element of 𝔽[X]<n is described by its n coefficients or by its n values on H; passage between these two coordinate systems is a linear isomorphism, the specialisation to H of the evaluation isomorphism for general nodes in 5.32.

Definition 9.26 (Evaluation map).

The evaluation map on H is the 𝔽-linear map (8.18)

evH:𝔽⁢[X]<n⟶𝔽n,evH⁢(f)=(f⁢(ω0),f⁢(ω1),…,f⁢(ωn−1)).

Linearity is immediate from (af+bg)(ωi)=af(ωi)+bg(ωi), an instance of 5.16.

Theorem 9.27 (Evaluation and interpolation are mutually inverse).

The evaluation map evH is a vector-space isomorphism. Its inverse is the interpolation map

intH:𝔽n⟶𝔽⁢[X]<n,intH⁢(v0,…,vn−1)=∑i=0n−1vi⁢Li⁢(X).

That is, intH∘evH=id𝔽⁢[X]<n and evH∘intH=id𝔽n.

Proof.

Both maps are linear and act between spaces of the same finite dimension n, so verifying one composition would suffice (a one-sided inverse makes evH injective, hence surjective by rank–nullity, 8.19); we verify both. For v∈𝔽n, the polynomial intH(v)=∑iviLi has value ∑iviLi(ωj)=vj at ωj by 9.21, so evH(intH(v))=v. For f∈𝔽[X]<n, the polynomial intH(evH(f))=∑if(ωi)Li is, by the uniqueness clause of 9.21, the unique degree-<n polynomial taking the values f(ωi) on H—which is f itself. Hence the two maps are inverse; in particular evH is bijective and linear, i.e. an isomorphism (8.18). □

In coordinates, evH is given by a matrix, which identifies evaluation on H with the Fourier transform. Matrix notation is fixed as follows: an n×n matrix over 𝔽 is a doubly indexed family A=(Ai⁢k)0≤i,k≤n−1 of elements of 𝔽, acting on a vector c∈𝔽n by (A⁢c)i=∑kAi⁢kck—the general form, written out through the standard basis (Example 8.15), of a linear map 𝔽n→𝔽n. The product of two matrices is defined so that (AB)c=A(Bc), which forces (A⁢B)i⁢j=∑kAi⁢kBk⁢j; the identity matrix I, with entries δi⁢k, acts as the identity map; and A is invertible if some matrix A−1 satisfies A−1A=AA−1=I.

Definition 9.28 (Vandermonde / DFT matrix).

Let f(X)=∑k=0n−1ckXk have coefficient vector c=(c0,…,cn−1). Then evH(f) has i-th entry f(ωi)=∑kckωi⁢k. Thus, relative to the monomial basis on 𝔽[X]<n and the standard basis on 𝔽n, the Vandermonde matrix

V=(ωi⁢k)0≤i,k≤n−1=(111⋯11ωω2⋯ωn−11ω2ω4⋯ω2⁢(n−1)⋮⋮1ωn−1ω2⁢(n−1)⋯ω(n−1)2)

—rows indexed by the evaluation point ωi, columns by the power k—represents evH, so that evH(f)=Vc. We call V the (discrete Fourier) transform matrix on H.

Theorem 9.29 (Invertibility and the inverse transform).

The matrix V of 9.28 is invertible, with

(V−1)k,i=1n⁢ω−i⁢k.

Equivalently, V−1=1nV¯, where V¯=(ω−i⁢k)i,k is the transform matrix built from ω−1 (itself a primitive n-th root of unity). Consequently the coefficient and value representations are related by the mutually inverse formulas

ck=1n⁢∑i=0n−1f⁢(ωi)⁢ω−i⁢k,f⁢(ωi)=∑k=0n−1ck⁢ωi⁢k.
Proof.

First, ω−1=ωn−1 has order n by Corollary 3.23 (with gcd(n−1,n)=1), so V¯ is again a matrix of the shape in 9.28. We show V¯V=nI. The (k,k′) entry of V¯V is

∑i=0n−1ω−i⁢k⁢ωi⁢k′=∑i=0n−1ωi⁢(k′−k).

By 9.16 this sum is n if n∣(k′−k) and 0 otherwise; for k,k′∈{0,…,n−1} we have n∣(k′−k)⇔k=k′. Hence V¯V=nI, and the same computation with the roles of the two factors exchanged gives VV¯=nI. Since n≠0 in 𝔽 (9.13), we may divide by n: V−1=1nV¯. The component formulas write out the matrix identities evH(f)=Vc and c=V−1evH(f). □

Remark 9.30.

9.27 and 9.29 state one isomorphism in abstract and in matrix form. Since the inverse of V is, up to the scalar 1/n, the same matrix with ω replaced by ω−1, the fast inverse transform of 9.37 costs as much as the forward one.

9.6 The number-theoretic transform and convolution

The map evH, read as the matrix V, is the discrete Fourier transform over a finite field rather than over ℂ; since it involves no analytic structure (no complex exponentials, no convergence), it is called the number-theoretic transform.

Definition 9.31 (Number-theoretic transform).

Let ω be a primitive n-th root of unity in 𝔽. The number-theoretic transform (NTT) sends the coefficient vector of a polynomial to its value vector on H: it is the evaluation map evH written in coordinates. Explicitly, the NTT of a=(a0,…,an−1)∈𝔽n is a^=(a^0,…,a^n−1) with

a^j=∑k=0n−1ak⁢ωj⁢k,j=0,…,n−1,

each entry being the value at ωj of the polynomial with coefficients a. The inverse number-theoretic transform is interpolation—the recovery of the coefficients from the values—and by 9.29 it too is a single explicit sum:

ak=1n⁢∑j=0n−1a^j⁢ω−j⁢k.

The NTT has the convolution property of the classical DFT, the basis of fast polynomial multiplication. The coefficients of a product are a convolution: with f=∑iaiXi and g=∑jbjXj, the coefficient of Xk in fg is ∑i+j=kaibj (5.3). The cyclic variant folds indices modulo n: for a,b∈𝔽n, the cyclic convolution a∗b∈𝔽n has entries

(a∗b)k=∑0≤i,j≤n−1i+j≡k(modn)ai⁢bj,k=0,…,n−1.
Theorem 9.32 (Convolution theorem).

For f,g∈𝔽[X]<n with degf+degg<n, let c=fg be their product (of degree <n). Then for every h∈H,

c⁢(h)=f⁢(h)⁢g⁢(h),

i.e. pointwise multiplication of value vectors corresponds to polynomial multiplication. Equivalently, writing a,b∈𝔽n for the coefficient vectors of f,g (padded with zeros up to length n),

a∗b^j=a^j⁢b^j(j=0,…,n−1),

so the NTT turns convolution into entrywise multiplication.

Proof.

The first identity is the statement that evaluation at h is a ring homomorphism 𝔽[X]→𝔽 (5.16): (fg)(h)=f(h)g(h). Since deg(fg)<n, interpolation recovers the product c=fg from its values on the n-point set H (9.21), so the entrywise product of the value vectors uniquely determines c.

The convolution statement is proved in three steps: (i) multiplication in 𝔽[X]/(Xn−1) is cyclic convolution of coefficient vectors; (ii) evaluation on H is a ring isomorphism from that quotient onto 𝔽n with entrywise operations; (iii) the degree bound rules out wrap-around, so the cyclic product is the ordinary one. For (i), work in the quotient ring 𝔽[X]/(Xn−1) (4.19 and 4.20, applied to the ideal of multiples of Xn−1, 4.17). Every class has a unique representative of degree <n, by division with remainder (5.12); and multiplying two such representatives and reducing replaces each Xk with k≥n by Xk−n, since Xn≡1. The coefficient of Xk in the reduced product of the representatives with coefficient vectors a and b is therefore ∑i+j≡k⁢(mod⁢n)aibj=(a∗b)k: multiplication in 𝔽[X]/(Xn−1) is cyclic convolution of coefficient vectors.

Next consider the map [p]↦evH(p) from 𝔽[X]/(Xn−1) to 𝔽n, where 𝔽n is a commutative ring under entrywise addition and multiplication (the ring laws hold in each coordinate because they hold in 𝔽), with multiplicative identity (1,…,1). The map is well defined: two representatives of a class differ by a multiple of Xn−1, which vanishes on H (9.13). It is a ring homomorphism (4.21), because evaluation at each point of H is one (5.16) and the operations on 𝔽n are entrywise. And it is bijective: classes correspond to their degree-<n representatives, on which evH is a bijection by 9.27. Hence it is a ring isomorphism 𝔽[X]/(Xn−1)→∼𝔽n, and it sends the product of the classes of f and g—coefficient vector a∗b—to the entrywise product of a^ and b^. This is the displayed identity. Finally, when degf+degg<n, the ordinary product fg already has degree <n, so no folding occurs, the cyclic and ordinary products coincide, and the statement computes fg itself. □

Remark 9.33 (Computational significance).

9.32 reduces multiplying two degree-<n/2 polynomials—a quadratic-cost operation by the schoolbook method—to: transform both (NTT), multiply the value vectors entrywise (n multiplications), and transform back (inverse NTT). If the NTT runs in O(nlogn) operations, the whole multiplication costs O(nlogn). The fast Fourier transform, constructed below, meets that hypothesis.

Example 9.34 (The convolution theorem in 𝔽17).

In 𝔽17, the element ω=4 has ω2=16=−1, so it is a primitive 4-th root of unity with domain H={1,4,16,13}. To multiply f=1+2X and g=3+X, pad both coefficient vectors to length 4 and transform: a^=(3,9,16,10) and b^=(4,7,2,16), the values of f and of g on H. Multiplying entrywise gives (12,12,15,7), the values of fg on H, and the inverse transform returns (3,7,2,0): the coefficients of fg=3+7X+2X2, agreeing with the schoolbook product. At n=4 nothing is saved; the example exhibits the three-step procedure, which saves work once the transforms themselves cost O(nlogn) (§9.7).

9.7 The fast Fourier transform

Computing a^=Va directly from 9.28 costs Θ(n2) field multiplications: each of the n outputs is a sum of n products. The fast Fourier transform (FFT)—here a number-theoretic FFT—computes the same vector in O(nlogn) operations by a divide-and-conquer recursion, provided n is a power of two or, more generally, smooth (9.10).

Theorem 9.35 (Cooley–Tukey radix-2 step).

Suppose n=2m and ω is a primitive n-th root of unity in 𝔽. Given f(X)=∑k=0n−1akXk, split its coefficients by parity into

feven⁢(Y)=∑k=0m−1a2⁢k⁢Yk,fodd⁢(Y)=∑k=0m−1a2⁢k+1⁢Yk,

so that f(X)=feven(X2)+Xfodd(X2). Then η:=ω2 is a primitive m-th root of unity, and for j=0,…,m−1,

f⁢(ωj) =feven⁢(ηj)+ωj⁢fodd⁢(ηj), (7)
f⁢(ωj+m) =feven⁢(ηj)−ωj⁢fodd⁢(ηj). (8)

Thus the length-n NTT of a reduces to two length-m NTTs (of the even and odd coefficient subsequences, over the domain ⟨η⟩) plus O(n) extra operations.

Proof.

The identity f(X)=feven(X2)+Xfodd(X2) regroups the sum ∑kakXk into even-index and odd-index terms; in the odd terms one factor of X is pulled out, leaving powers X2⁢k. That η=ω2 is a primitive m-th root of unity follows from 9.5 and the order-of-a-power formula (Corollary 3.23): ord(ω2)=n/gcd(2,n)=n/2=m, using 2∣n.

It remains to evaluate. For (7), put X=ωj; then X2=ω2⁢j=ηj, so f(ωj)=feven(ηj)+ωjfodd(ηj). For (8), put X=ωj+m; then X2=ω2⁢j+2⁢m=ω2⁢jωn=ηj⋅1=ηj (since 2m=n and ωn=1), while the linear factor is ωj+m=ωjωm=−ωj. Here ωm=−1, because ωm has order n/gcd(m,n)=n/m=2 (Corollary 3.23), and −1 is the unique element of order 2 in a field: x2=1 with x≠1 forces (x−1)(x+1)=0 and so x=−1; and −1≠1, since char𝔽∤n (9.13) with n even forces char𝔽≠2. Substituting, f(ωj+m)=feven(ηj)−ωjfodd(ηj). □

Remark 9.36 (The butterfly).

Equations (7)–(8) constitute the butterfly: from the two subtransform outputs Ej=feven(ηj) and Oj=fodd(ηj) one forms the twiddle tj=ωjOj and reads off the two outputs Ej+tj and Ej−tj. In a diagram, Ej and Oj are two nodes on the left, each joined to both outputs on the right, the two Ej-edges with weight 1 and the two Oj-edges with weights +ωj and −ωj; the pair of crossing edges forms the × after which the operation is named. Each butterfly costs one multiplication (the twiddle) and two additions, and there are n/2 of them per level.

Theorem 9.37 (O(nlogn) cost of the FFT).

Let n=2t and let T(n) be the number of field additions and multiplications the radix-2 recursion of 9.35 uses to compute a length-n NTT. Then

T⁢(n)=2⁢T⁢(n/2)+c⁢n(n>1),T⁢(1)=O⁢(1),

for a constant c, and therefore T(n)=O(nlogn). The inverse NTT has the same cost, since it is the forward NTT with ω replaced by ω−1, followed by scaling each entry by 1/n (9.29).

Proof.

The recursion is exactly 9.35: a length-n transform calls two length-n/2 transforms (on the even and odd coefficient subsequences) and combines them with n/2 butterflies of O(1) operations each, for the cn overhead. Unrolling, with n=2t,

T⁢(2t)=2⁢T⁢(2t−1)+c⁢ 2t.

Divide by 2t and set S(t)=T(2t)/2t: then S(t)=S(t−1)+c, so S(t)=S(0)+ct=O(1)+ct, and T(2t)=2tS(t)=O(2t)+ct 2t=O(t 2t). With t=log2n this is T(n)=O(nlogn). (Equivalently: the recursion tree has log2n levels, each performing Θ(n) total work across all subproblems at that level.) The inverse-transform claim is 9.29: the inverse is the same Cooley–Tukey recursion with ω−1 in place of ω (also a primitive n-th root of unity), plus a final pass of n divisions by n, all within O(nlogn). □

Remark 9.38 (Mixed radix and smoothness).

Fast transforms apply when n is smooth and the field contains a primitive n-th root of unity, that is, n∣q−1 (9.7); for a power-of-two n dividing q−1, every level of the recursion is a radix-2 step.

Example 9.39 (A length-4 transform).

Take n=4 with primitive 4-th root ω (so ω2=−1 and ω4=1, and η=ω2=−1 is the primitive 2nd root). For f=a0+a1X+a2X2+a3X3, the two length-2 subtransforms over the domain {1,−1}—each itself a single butterfly, with twiddle η0=1—are

E=(a0+a2,a0−a2),O=(a1+a3,a1−a3),

and the butterflies give

a^0=E0+ω0⁢O0,a^2=E0−ω0⁢O0,a^1=E1+ω1⁢O1,a^3=E1−ω1⁢O1.

(Outputs j and j+m are paired, as in (7)–(8).) This uses 2 subtransforms of 2 additions each plus 2 butterflies of 2 additions each (n/2=2 per level, 9.36)—together 2 twiddle multiplications and 8 additions—versus 16 coefficient-products and 12 additions for the direct 4×4 matrix multiply; the difference grows with n.

Refer to caption
Figure 4: The length-4 transform of 9.39 as a circuit. The inputs split by parity into two length-2 subtransforms, whose outputs E0,E1 and O0,O1 feed the two butterflies of 9.36: each Ej is carried to outputs a^j and a^j+2 with weight 1, each Oj with weights +ωj and −ωj (7–8); the crossing pair of weighted edges is the × after which the butterfly is named.

9.8 The role of smooth multiplicative domains in polynomial proof systems

This subsection states how the preceding results are used in Halo 2, the proof system of Orchard, which encodes a computation as polynomial identities on the evaluation domain H=μn: the n-step table described at the start of this section is indexed by the n points of H.

Remark 9.40 (The roles played by H, ZH, the Lagrange basis, and the FFT).
  • •

    Witnesses as evaluations on H. A prover lays out the trace of a computation as the values of one or more polynomials on the n points of H. By 9.27 this is the same data as a polynomial of degree <n; the prover may move freely between the value (Lagrange) representation, suited to stating constraints row by row, and the coefficient representation, suited to committing and to low-degree testing. The change of representation is the (inverse) NTT.

  • •

    Constraints as divisibility by ZH. “Constraint polynomial C holds on every row” means C vanishes on all of H, which by 9.13 means exactly that ZH=Xn−1 divides C. The prover demonstrates this by exhibiting a quotient t with C(X)=t(X)(Xn−1). The closed form ZH(X)=Xn−1, evaluated by one exponentiation, makes this check cheap at a random point. 9.14 extends the same technique to cosets γH, used to separate quotient and remainder domains.

  • •

    Lagrange selectors. The Lagrange polynomials Li of 9.20 are selectors: Li is 1 on row i and 0 elsewhere (9.21), so boundary and instance constraints (e.g. “the first row equals the public input”) become L0⋅(…). The closed form and the barycentric formula (9.22, 9.23) let the verifier evaluate these at a random challenge in O(n) or even O(logn) field operations rather than reconstructing polynomials.

  • •

    Group structure for permutations and shifts. Because H is a cyclic group (9.11), multiplication by ω is the cyclic “next-row” shift ωi↦ωi+1. Constraints relating a row to its neighbour become f(ωX) versus f(X); permutation arguments, on which Halo 2’s copy constraints are built, rest on the action of the group on itself and on its cosets. An arbitrary set of n points has none of this structure.

  • •

    Smoothness for speed. Provers manipulate polynomials of size n (often after enlarging the domain by a small constant factor for low-degree testing). Transforms between representations, multiplications and coset evaluations are computed by NTTs, which by 9.37 cost O(nlogn) instead of O(n2) (at the sizes used in practice, the difference between feasible and infeasible computation), provided n is smooth and 𝔽q contains a primitive n-th root of unity. By 9.7 that requires n∣q−1; by 9.10 this is why high-two-adicity primes are chosen for the scalar fields of the Pallas and Vesta curves (10).