Fast Evaluation on an Affine Tower

Status: Conditional algorithmic theorem

This chapter gives a recursive algorithm for evaluating a polynomial written in the affine kernel basis. If a compatible affine quadratic domain tower of size $N=2^m$ is supplied, the algorithm uses $O(N\log N)$ field operations.

The recursion and its operation count are established. The conclusion is conditional because the existence of a tower of the requested size is a separate arithmetic question.

10.1 Compatible algebraic and domain data

Let $\mathbb{F}$ be a field of characteristic different from $2$. Fix $m\ge 0$ and let $N=2^m$.

Assume that we are given an affine quadratic domain tower

$$D_0⟶D_1⟶\cdots ⟶D_m$$

with

$$|D_i|=2^{m-i}.$$

At level $i$, the tower map is

$${\pi }_i(x)=\frac{x^2-v_i}{u_i},u_i\in {\mathbb{F}}^{\times },$$

and every point of $D_{i+1}$ has a fiber $\{\alpha ,-\alpha \}\subseteq D_i$ with $\alpha \ne 0$.

Use the same parameters to define the affine coordinates

$$X_0=X,X_{i+1}=\frac{X_i^2-v_i}{u_i}.$$

The compatibility between the coordinate recursion and the domain maps is essential: when $\alpha \in D_0$, the value $X_i(\alpha )$ lies in $D_i$.

10.2 Input representation

Let

$$f(X)=\sum _{y\in {\mathbb{B}}_m}{\lambda }_y{K}_y^{\mathrm{aff}}(X),$$

where

$$K_y^{\mathrm{aff}}(X)=\prod _{i=0}^{m-1}(X_i+y_i).$$

The input is the table of $N$ affine kernel coefficients

$$({\lambda }_y{)}_{y\in {\mathbb{B}}_m}.$$

The output is the ordered evaluation table

$$(f(\alpha ){)}_{\alpha \in D_0}.$$

The algorithm assumes that every domain level is stored together with its two-point fibers. Searching for fibers is not included in the evaluation cost.

10.3 First coefficient split

Write each Boolean index as

$$y=(y_0,z),y_0\in {\mathbb{B}}_1,z\in {\mathbb{B}}_{m-1}.$$

Define the tail kernel

$$K_z^{\mathrm{tail}}(X_1)=\prod _{i=1}^{m-1}(X_i+y_i).$$

Then

$$\begin{array}{rl}f(X_0)=& \sum _z{\lambda }_{0,z}{X}_0{K}_z^{\mathrm{tail}}(X_1)\\ & +\sum _z{\lambda }_{1,z}(X_0+1)K_z^{\mathrm{tail}}(X_1).\end{array}$$

Define two tail polynomials

$$A(X_1)=\sum _z{A}_z{K}_z^{\mathrm{tail}}(X_1)$$

and

$$B(X_1)=\sum _z{B}_z{K}_z^{\mathrm{tail}}(X_1),$$

with coefficient tables

$$A_z={\lambda }_{1,z}$$

and

$$B_z={\lambda }_{0,z}+{\lambda }_{1,z}.$$

It follows that

$$f(X_0)=A(X_1)+X_{0}B(X_1).$$

Proposition 10.1 — Affine-kernel coefficient split

For each $z\in {\mathbb{B}}_{m-1}$, the first recursive split is

$$({\lambda }_{0,z},{\lambda }_{1,z})⟼(A_z,B_z)=({\lambda }_{1,z},{\lambda }_{0,z}+{\lambda }_{1,z}).$$

The complete split uses exactly $N/2$ field additions and no field multiplications.

This inexpensive update is the reason for using affine kernel coordinates. In the ordinary monomial basis, the affine substitution would introduce binomial expansions of shifted powers.

10.4 One value butterfly

Let $\{\alpha ,-\alpha \}$ be the fiber over $\beta \in D_1$. Since $X_1(\alpha )=X_1(-\alpha )=\beta$,

$$f(\alpha )=A(\beta )+\alpha B(\beta )$$

and

$$f(-\alpha )=A(\beta )-\alpha B(\beta ).$$

Given $A(\beta )$ and $B(\beta )$, computing both outputs uses exactly:

• one multiplication, to form $\alpha B(\beta )$; and
• two additions or subtractions.

The result does not depend on which member of the fiber is named $\alpha$.

10.5 Recursive algorithm

The two tail polynomials $A$ and $B$ are expressed in the affine kernel basis associated with the shortened coordinate sequence

$$X_1,X_2,\dots ,X_{m-1}.$$

They can therefore be evaluated recursively on $D_1$ using the remaining tower levels.

The recursive procedure is:

AffineKernelEval(level i, coefficient table lambda):
    n := length(lambda)

    if n = 1:
        return the one constant value

    for each tail index z:
        A[z] := lambda[1,z]
        B[z] := lambda[0,z] + lambda[1,z]

    values_A := AffineKernelEval(level i+1, A)
    values_B := AffineKernelEval(level i+1, B)

    for each stored fiber {alpha,-alpha} over beta in D_(i+1):
        t := alpha * values_B[beta]
        values_f[alpha]  := values_A[beta] + t
        values_f[-alpha] := values_A[beta] - t

    return values_f

The base case contains the empty tail kernel, which is the constant polynomial $1$. Hence the sole remaining coefficient is already the value on the one-point final domain.

Theorem 10.2 — Correctness

Given compatible affine coordinates and an affine quadratic domain tower, the algorithm returns $f(\alpha )$ for every $\alpha \in D_0$.

Proof

Proceed by induction on $m$. The claim is immediate when $m=0$.

For $m>0$, Proposition 10.1 gives the polynomial identity

$$f(X_0)=A(X_1)+X_{0}B(X_1).$$

The induction hypothesis correctly evaluates $A$ and $B$ on $D_1$. For each fiber $\{\alpha ,-\alpha \}$ over $\beta$, the value butterfly then computes $f(\alpha )$ and $f(-\alpha )$. The fibers partition $D_0$, so every requested evaluation is returned. $\square$

10.6 Exact arithmetic cost

Let $M(N)$ be the number of field multiplications and let $A(N)$ be the number of field additions or subtractions.

At a problem of size $N>1$:

• the coefficient split uses $N/2$ additions;
• the two recursive calls have size $N/2$;
• the value butterflies use $N/2$ multiplications and $N$ additions or subtractions.

Therefore

$$M(N)=2M(N/2)+\frac{N}{2},M(1)=0,$$

and

$$A(N)=2A(N/2)+\frac{3N}{2},A(1)=0.$$

Theorem 10.3 — Exact evaluation cost

For $N=2^m$, the recursive affine-kernel evaluation uses exactly

$$M(N)=\frac{mN}{2}$$

field multiplications and

$$A(N)=\frac{3mN}{2}$$

field additions or subtractions.

Proof

At every recursion depth, the subproblem sizes sum to $N$. Thus each of the $m$ nontrivial depths uses $N/2$ multiplications and $3N/2$ additions or subtractions. Summing over all depths gives the formulas. $\square$

Consequently, the arithmetic complexity is

$$O(N\log N).$$

These counts exclude:

• construction or discovery of the affine tower;
• validation and ordering of its fibers;
• conversion from another polynomial basis;
• memory movement and indexing; and
• hashing, commitments, or proof-protocol operations.

Multiplication by a precomputed domain element is counted as one field multiplication.

10.7 What the condition replaces

A classical radix-two FFT usually assumes a multiplicative subgroup or coset supporting the required chain of squaring maps. The affine algorithm does not require $D_0$ itself to be such a subgroup.

However, the subgroup assumption is not removed without replacement. It is replaced by the requirement that compatible sets

$$D_0,D_1,\dots ,D_m$$

and two-to-one affine quadratic maps between them are available. Whether that requirement can be met is field- and size-dependent.

Thus the correct implication is:

$$\text{valid compatible affine tower}⟹\text{affine-kernel evaluation in }O(N\log N).$$

The converse is not asserted, and universal tower existence is not assumed.

10.8 Relation to interpolation and protocols

The evaluation map is invertible because the points of $D_0$ are distinct and the affine kernels form a basis. Therefore interpolation exists as a linear operation.

This chapter does not yet provide or count a recursive interpolation algorithm. It also does not prove a proximity property, an error-correction guarantee, or protocol soundness. Those questions require separate analysis.

10.9 What has been established

Conditional on a supplied compatible affine tower, this chapter establishes:

• the affine-kernel coefficient split;
• the recursive evaluation algorithm and its correctness;
• an exact cost of $mN/2$ multiplications;
• an exact cost of $3mN/2$ additions or subtractions; and
• total arithmetic complexity $O(N\log N)$.

No universal tower-construction, interpolation-complexity, proximity, or soundness theorem is asserted.