Additive NTT

This article aims to intuitively explain the goals and process of the Additive NTT protocol.

Introduction

Binius is a SNARK constructed using a characteristic-2 finite field. In Binius, RS-encoding (Reed-Solomon encoding) is employed, but there is a challenge: the conventional Radix-2 FFT cannot be utilized in characteristic-2 finite fields. This paper addresses that challenge.

The title of the paper is "Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes." A characteristic-2 finite field is an extension field of the form F2r\mathbb{F}_{2^r}​, which can be constructed as a polynomial ring. Traditionally, polynomials are represented using the Monomial Basis 1,X,X2,1, X, X^2, \dotswhich is a natural choice. However, this paper introduces an ingenious new polynomial basis and proposes an encoding algorithm that achieves performance comparable to the Radix-2 FFT.

Background

Radix-2 FFT

The coefficient form of a univariate polynomial of degree n1n−1 is defined as:

P(X)=c0+c1X+c2X2++cn1Xn1P(X) = c_0 + c_1X + c_2X^2 + \cdots + c_{n-1}X^{n-1}

where the basis is {1,X,X2,,Xn1}\{1, X, X^2, \dots, X^{n-1}\}.

On the other hand, the evaluation form of a univariate polynomial is defined as:

P(X)=P(x0)L0(X)+P(x1)L1(X)+P(x2)L2(X)++P(xn1)Ln1(X)P(X) = P(x_0)\cdot L_0(X) + P(x_1)\cdot L_1(X) + P(x_2)\cdot L_2(X) + \cdots + P(x_{n-1})\cdot L_{n-1}(X)

where the basis is {L0(X),L1(X),L2(X),,Ln1(X)}\{L_0(X), L_1(X), L_2(X), \dots, L_{n-1}(X)\}, called the Lagrange basis.

In Radix-2 FFT (Fast Fourier Transform), a Lagrange basis is constructed using the roots of unity. Each basis polynomial Li(X)L_i(X) is defined as:

Li(X)=jiXωjωiωj={1 if X=ωi0 otherwiseL_i(X) = \prod_{j \ne i}\frac{X - \omega^j}{\omega^i - \omega^j} = \begin{cases} 1 &\text{ if }X = \omega^i \\ 0 &\text{ otherwise} \end{cases}

Since we use finite fields instead of complex numbers, this is technically a Radix-2 NTT (Number Theoretic Transform), but for simplicity, we'll refer to it as FFT. Radix-2 FFT transforms a polynomial in coefficient form into its evaluation form. The matrix used to multiply the coefficient vector is called a Vandermonde matrix:

[P(1)P(ω)P(ω2)P(ωn1)]=[11111ωω2ωn11ω2ω4ω2(n1)1ωn1ω2(n1)ω(n1)2][c0c1c2cn1]\begin{bmatrix} P(1)\\ P(\omega)\\ P(\omega^2)\\ \vdots \\ P(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)^2} \end{bmatrix} \cdot \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ \vdots \\ c_{n-1} \end{bmatrix}

The nn-th roots of unity satisfy:

ωn1=(ωn/21)(ωn/2+1)=0\omega^n - 1 = (\omega^{n/2} - 1)(\omega^{n/2} + 1) = 0

Since ωn/2\omega^{n/2} cannot equal 11, it must equal 1-1.

Using the property of ωn/2=1\omega^{n/2} = -1, Radix-2 FFT is efficiently computed via the Cooley-Tukey algorithm. The polynomial P(X)P(X) is divided into two parts:

  • PE(X2)P_E​(X^2): even powers of XX.

  • PO(X2)P_O(X^2): odd powers of XX.

This gives:

P(X)=PE(X2)+XPO(X2)P(X) = P_{E}(X^2) + X \cdot P_{O}(X^2)

For X=XX = -X,substituting Xωn/2X \cdot \omega^{n/2}, we have:

P(X)=P(Xωn/2)=PE(X2)XPO(X2)P(-X) = P(X \cdot \omega^{n/2}) = P_E(X^2) - X\cdot P_O(X^2)

This transforms an nn-point FFT problem into two n/2n / 2-point FFT problems.

Define Δim(X)\Delta^m_i(X) as follows:

Δim(X)={Δi+1m(X)+X2iΔi+1m+2i(X) if 0i<log2ncm if i=log2n\Delta^m_i(X) = \begin{cases} \Delta^m_{i+1}(X) + X^{2^i}\Delta^{m + 2^i }_{i+1}(X) & \text{ if }0 \le i < \log_2 n \\ c_m & \text{ if }i = \log_2 n\\ \end{cases}

For example, for n=8n=8, the recursive computation proceeds as such:

P(X)=i=07ciXi=c0+c4X4+X2(c2+c6X4)+X(c1+c5X4+X2(c3+c7X4)=Δ20(X)+X2Δ22(X)+X(Δ21(X)+X2Δ23(X))=Δ10(X)+XΔ11(X)=Δ00(X)\begin{align*} P(X) &= \sum_{i = 0}^{7}c_iX_i \\ &= c_0 + c_4X^4 + X^2(c_2 + c_6X^4) + X(c_1 + c_5X^4 + X^2(c_3 + c_7X^4)\\ &= \Delta^0_2(X) + X^2\Delta^2_2(X) + X(\Delta^1_2(X) + X^2\Delta^3_2(X)) \\ &=\Delta^0_1(X) + X\Delta^1_1(X) \\ &=\Delta^0_0(X) \end{align*}

By recursively applying this process, the computational complexity of FFT becomes O(nlogn)O(n \cdot \log n).

The Inverse FFT (IFFT) converts a polynomial from its evaluation form back to its coefficient form by using the inverse of the Vandermonde matrix:

[c0c1c2cn1]=[11111ωω2ωn11ω2ω4ω2(n1)1ωn1ω2(n1)ω(n1)2]1[P(1)P(ω)P(ω2)P(ωn1)]\begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ \vdots \\ c_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)^2} \end{bmatrix}^{-1} \cdot \begin{bmatrix} P(1)\\ P(\omega)\\ P(\omega^2)\\ \vdots \\ P(\omega^{n-1}) \end{bmatrix}

The IFFT can also be computed in O(nlogn)O(n \cdot \log n) using a similar recursive approach to FFT.

2-adicity

When the modulus of a prime field is of the form 2ST+12^S\cdot T + 1, a 2k2^k-th root of unity ω\omega for k<Sk < S can be determined as follows.

gp1=g2ST=(g2SkT)2k=ω2k1(modp)g^{p-1} = g^{2^S \cdot T} = (g^{2^{S-k} \cdot T})^{2^k} = \omega^{2^k} \equiv 1 \pmod p

In other words, if the order of the multiplicative subgroup Fp×\mathbb{F}_p^\times​ of a prime field is of the form 2ST2^S \cdot T, and SS (also known as the 2-adicity) is large, FFT can be used effectively. Fields with this structure are referred to as FFT-friendly fields.

What about characteristic-2 finite fields, such as F2r\mathbb{F}_{2^r}​? For these fields, the order of the multiplicative subgroup F2r×\mathbb{F}_{2^r}^{\times} is 2r12^r - 1. Since the 2-adicity of 2r12^r - 1 is 0, Radix-2 FFT cannot be used.

This naturally raises the question: when the characteristic is 2, what new polynomial basis would be suitable? Moreover, to achieve fast computation similar to Radix-2 FFT, the method must recursively reduce the problem into smaller subproblems.Protocol Explanation

NOTE: From this point onward, ω\omega is no longer a root of unity, and Δ\Delta will be newly defined.

Polynomial Basis

The elements of F2r\mathbb{F}_{2^r} can be represented as the set {ωi}i=02r1\{\omega_i\}_{i=0}^{2^r - 1}, where:

i=k=0r1ik2k,ik0,1i = \sum_{k = 0}^{r-1}i_k \cdot 2^k, \forall i_k \in {0,1}

Given a basis vector v={v0,,vr1}v = \{v_0, \dots, v_{r-1}\} composed of elements from F2r\mathbb{F}_{2^r}, each ωi\omega_i can be expressed as:

ωi=k=0r1ikvk\omega_i = \sum_{k = 0}^{r-1}i_k \cdot v_k

We define the subspace vanishing polynomial as:

Wj(X)=i=02j1(X+ωi), where 0jr1W_j(X) = \prod_{i=0}^{2^j-1}(X + \omega_i)\text{, where } 0 \le j \le r - 1

This mean the full form of the vanishing polynomials Wj(X)W_j(X) are as follows:

W0(X)=X+ω0,W1(X)=(X+ω0)(X+ω1),W2(X)=(X+ω0)(X+ω1)(X+ω2)(X+ω3),W_0(X) = X + \omega_0, \\ W_1(X) = (X + \omega_0)(X + \omega_1) ,\\ W_2(X) = (X + \omega_0)(X + \omega_1)(X + \omega_2)(X + \omega_3) ,\\

and so on.

Thus, deg(Wj(X))=2j\deg(W_j(X)) = 2^j and the roots of W2(X)W_2(X) are ω0,ω1,ω2,ω3\omega_0, \omega_1, \omega_2, \omega_3 . This follows from the fact that addition in F2r\mathbb{F}_{2^r}​ is XOR, so ωi+ωi=0\omega_i + \omega_i = 0, a direct result of the field’s characteristic being 2.

Lemma 1. Wj(X)W_j(X) is a F2\mathbb{F}_2-linearized polynomial.

Wj(X)=i=0jaj,iX2i, where aj,iF2rW_j(X) = \sum_{i = 0}^{j}a_{j,i}X^{2^i} \text{, where }a_{j,i} \in \mathbb{F}_{2^r}

Furthermore, Wj(X)W_j(X) satisfies the following property:

Wj(X+Y)=Wj(X)+Wj(Y),X,YF2rW_j(X + Y) = W_j(X) + W_j(Y), \forall X,Y \in \mathbb{F}_{2^r}

We now define a new polynomial basis Xi(X)X_i(X) as:

Xi(X)=j=0r1(Wj(X)Wj(ω2j))ijX_i(X) = \prod_{j= 0}^{r-1}(\frac{W_j(X)}{W_j(\omega_{2^j})})^{i_j}

where:

i=j=0r1ij2j,ij0,1i = \sum_{j = 0}^{r-1}i_j \cdot 2^j, \forall i_j \in {0,1}

The new polynomial basis Xi(X)X_i(X) is as follows:

X0(X)=1,X1(X)=W0(X)W0(ω1)=X+ω0ω1+ω0,X2(X)=W1(X)W1(ω2)=(X+ω0)(X+ω1)(ω2+ω0)(ω2+ω1),X3(X)=W0(X)W1(X)W0(ω1)W1(ω2)=(X+ω0)2(X+ω1)(ω1+ω0)(ω2+ω0)(ω2+ω1),X4(X)=W2(X)W2(ω4)=(X+ω0)(X+ω1)(X+ω2)(X+ω3)(ω4+ω0)(ω4+ω1)(ω4+ω2)(ω4+ω3),X_0(X) = 1 , \\ X_1(X) = \frac{W_0(X)}{W_0(\omega_1)} = \frac{X + \omega_0}{\omega_1 + \omega_0} , \\ X_2(X) = \frac{W_1(X)}{W_1(\omega_2)} = \frac{(X + \omega_0)(X + \omega_1)}{(\omega_2 + \omega_0)(\omega_2 + \omega_1)}, \\ X_3(X) = \frac{W_0(X)W_1(X)}{W_0(\omega_1)W_1(\omega_2)} = \frac{(X + \omega_0)^2(X + \omega_1)}{(\omega_1 + \omega_0)(\omega_2 + \omega_0)(\omega_2 + \omega_1)} , \\ X_4(X) = \frac{W_2(X)}{W_2(\omega_4)} = \frac{(X + \omega_0)(X + \omega_1)(X + \omega_2)(X + \omega_3)}{(\omega_4 + \omega_0)(\omega_4 + \omega_1)(\omega_4 + \omega_2)(\omega_4 + \omega_3)},

and so on.

Thus, deg(Xi(X))=i\deg(X_i(X)) = i.

The coefficient form of an n1n-1-degree univariate polynomial [Dn](X)F2r[X]/(X2r1)[D_n](X) \in \mathbb{F}_{2^r}[X] / (X^{2^r} - 1) is expressed as:

[Dn](X)=d0+d1X1(X)+d2X2(X)++dn1Xn1(X)[D_n](X) = d_0 + d_1X_1(X) + d_2X_2(X) + \dots + d_{n-1}X_{n-1}(X)

The evaluation form of this polynomial is:

[Dn](X)=[Dn](ω0+ωl)L0l(X)+[Dn](ω1+ωl)L1l(X)+[Dn](ω2+ωl)L2l(X)++[Dn](ωn1+ωl)Ln1l(X)[D_n](X) = [D_n](\omega_0 + \omega_l) \cdot L^l_0(X) + [D_n](\omega_1 + \omega_l) \cdot L^l_1(X) + [D_n](\omega_2 + \omega_l) \cdot L^l_2(X) + \cdots + [D_n](\omega_{n-1} + \omega_l) \cdot L^l_{n-1}(X)

where Lil(X)L^l_i(X) is defined as:

Lil(X)=jiXωjωi+ωlωj={1 if X=ωi+ωl0 otherwiseL^l_i(X) = \prod_{j \ne i}\frac{X - \omega_j}{\omega_i + \omega_l - \omega_j} = \begin{cases} 1 &\text{ if }X = \omega_i + \omega_l \\ 0 &\text{ otherwise} \end{cases}

We denote the set of evaluations as D^nl\hat{D}^l_n, defined as such:

D^nl={[Dn](ω0+ωl),[Dn](ω1+ωl),[Dn](ω2+ωl),,[Dn](ωn1+ωl)}\hat{D}^l_n = \{[D_n](\omega_0 + \omega_l), [D_n](\omega_1 + \omega_l),[D_n](\omega_2 + \omega_l),\dots, [D_n](\omega_{n-1} + \omega_l) \}

Delta Polynomial

The recursive calculation of [Dn](X)[D_n](X) can be performed by defining Δim(X)\Delta^m_i(X) as follows:

Δim(X)={Δi+1m(X)+Wi(X)Wi(ω2i)Δi+1m+2i(X) if 0i<log2ndm if i=log2n\Delta^m_i(X) = \begin{cases} \Delta^m_{i+1}(X) + \frac{W_i(X)}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i+1}(X) & \text{ if }0 \le i < \log_2 n \\ d_m & \text { if } i = \log_2n \end{cases}

where 0m<2i0 \le m < 2^i.

For n=8n = 8, Δ\Delta exists as follows:

Δ30(X)=d0,Δ31(X)=d1,Δ32(X)=d2,,Δ37(X)=d7,Δ20(X)=Δ30(X)+W2(X)W2(ω4)Δ34(X)=d0+W2(X)W2(ω4)d4,Δ21(X)=Δ31(X)+W2(X)W2(ω4)Δ35(X)=d1+W2(X)W2(ω4)d5,Δ22(X)=Δ32(X)+W2(X)W2(ω4)Δ36(X)=d2+W2(X)W2(ω4)d6,Δ23(X)=Δ33(X)+W2(X)W2(ω4)Δ37(X)=d3+W2(X)W2(ω4)d7,Δ10(X)=Δ20(X)+W1(X)W1(ω2)Δ22(X),Δ11(X)=Δ21(X)+W1(X)W1(ω2)Δ23(X),Δ00(X)=Δ10(X)+W0(X)W0(ω1)Δ11(X)\Delta^0_3(X) = d_0,\Delta^1_3(X) = d_1, \Delta^2_3(X) = d_2, \dots, \Delta^7_3(X) = d_7, \\ \Delta^0_2(X) = \Delta^0_3(X) + \frac{W_2(X)}{W_2(\omega_4)} \Delta^4_3(X) = d_0 + \frac{W_2(X)}{W_2(\omega_4)}d_4, \\ \Delta^1_2(X) = \Delta^1_3(X) + \frac{W_2(X)}{W_2(\omega_4)} \Delta^5_3(X) = d_1 + \frac{W_2(X)}{W_2(\omega_4)}d_5, \\ \Delta^2_2(X) = \Delta^2_3(X) + \frac{W_2(X)}{W_2(\omega_4)} \Delta^6_3(X) = d_2 + \frac{W_2(X)}{W_2(\omega_4)}d_6, \\ \Delta^3_2(X) = \Delta^3_3(X) + \frac{W_2(X)}{W_2(\omega_4)} \Delta^7_3(X) = d_3 + \frac{W_2(X)}{W_2(\omega_4)}d_7, \\ \Delta^0_1(X) = \Delta^0_2(X) + \frac{W_1(X)}{W_1(\omega_2)} \Delta^2_2(X), \\ \Delta^1_1(X) = \Delta^1_2(X) + \frac{W_1(X)}{W_1(\omega_2)} \Delta^3_2(X), \\ \Delta^0_0(X) = \Delta^0_1(X) + \frac{W_0(X)}{W_0(\omega_1)} \Delta^1_1(X)

[Dn](X)[D_n](X) is equivalent to Δ00(X)\Delta^0_0(X). For example, [D8](X)[D_8](X) is recursively computed as follows:

[D8](X)=i=07diXi(X)=d0+d1W0(X)W0(ω1)+d2W1(X)W1(ω2)+d3W0(X)W1(X)W0(ω1)W1(ω2)+d4W2(X)W2(ω4)     d5W0(X)W2(X)W0(ω1)W2(ω4)+d6W1(X)W2(X)W1(ω2)W2(ω4)+d7W0(X)W1(X)W2(X)W0(ω1)W1(ω2)W2(ω4)=(d0+d4W2(X)W2(ω4)+W1(X)W1(ω2)(d2+d6W2(X)W2(ω4)))     +W0(X)W0(ω1)(d1+d5W2(X)W2(ω4)+W1(X)W1(ω2)(d3+d7W2(X)W2(ω4)))=(Δ20(X)+W1(X)W1(ω2)Δ22(X))+W0(X)W0(ω1)(Δ21(X)+W1(X)W1(ω2)Δ23(X))=Δ10(X)+W0(X)W0(ω1)Δ11(X)=Δ00(X)\begin{align*} [D_8](X) &= \sum_{i = 0}^{7} d_iX_i(X) \\ &=d_0 + d_1\frac{W_0(X)}{W_0(\omega_1)} + d_2\frac{W_1(X)}{W_1(\omega_2)} + d_3\frac{W_0(X)W_1(X)}{W_0(\omega_1)W_1(\omega_2)} + d_4\frac{W_2(X)}{W_2(\omega_4)} \\ &\space\space\space\space\space d_5\frac{W_0(X)W_2(X)}{W_0(\omega_1)W_2(\omega_4)} + d_6\frac{W_1(X)W_2(X)}{W_1(\omega_2)W_2(\omega_4)} + d_7\frac{W_0(X)W_1(X)W_2(X)}{W_0(\omega_1)W_1(\omega_2)W_2(\omega_4)} \\ &=\bigg(d_0 + d_4\frac{W_2(X)}{W_2(\omega_4)} + \frac{W_1(X)}{W_1(\omega_2)}\bigg( d_2 + d_6\frac{W_2(X)}{W_2(\omega_4)}\bigg)\bigg) \\ &\space\space\space\space\space + \frac{W_0(X)}{W_0(\omega_1)}\bigg(d_1 + d_5\frac{W_2(X)}{W_2(\omega_4)} + \frac{W_1(X)}{W_1(\omega_2)}\bigg(d_3 + d_7\frac{W_2(X)}{W_2(\omega_4)} \bigg) \bigg) \\ &=\bigg(\Delta^0_2(X) + \frac{W_1(X)}{W_1(\omega_2)}\Delta^2_2(X) \bigg) + \frac{W_0(X)}{W_0(\omega_1)}\bigg( \Delta^1_2(X) + \frac{W_1(X)}{W_1(\omega_2)}\Delta^3_2(X) \bigg) \\ &= \Delta^0_1(X) + \frac{W_0(X)}{W_0(\omega_1)}\Delta^1_1(X) \\ &= \Delta^0_0(X) \end{align*}

Lemma 2. Δim(X+Y)=Δim(X),Y{ωb}b=02i1\Delta^m_i(X + Y) = \Delta^m_i(X), \forall Y \in \{\omega_b\}_{b = 0}^{2^i - 1}

Proof:

Case 1: i=log2ni = \log_2 n, both Δim(X+Y)\Delta^m_i(X + Y) and Δim(X)\Delta^m_i(X) equal dmd_m, so the equality holds trivially.

Case 2: i=log2n1i = \log_2 n - 1, Δim(X)\Delta^m_i(X) is given as:

Δlog2n1m(X)=Δlog2nm(X)+Wlog2n1(X)Wlog2n1(ω2log2n1)Δlog2nm+2log2n1(X)=dm+Wlog2n1(X)Wlog2n1(ω2log2n1)dm+2log2n1\begin{align*} \Delta^m_{\log_2 n - 1}(X) &= \Delta^m_{\log_2 n}(X) + \frac{W_{\log_2 n - 1}(X)}{W_{\log_2 n - 1}(\omega_{2^{\log_2 n - 1}})} \Delta^{m + 2^{\log_2 n - 1}}_{\log_2 n}(X) \\ &= d_m + \frac{W_{\log_2 n - 1}(X)}{W_{\log_2 n - 1}(\omega_{2^{\log_2 n - 1}})} d_{m + 2^{\log_2 n - 1}} \end{align*}

which simplifies as follows:

Δlog2n1m(X+Y)=dm+Wlog2n1(X+Y)Wlog2n1(ω2log2n1)dm+2log2n1\Delta^m_{\log_2 n - 1}(X + Y) = d_m + \frac{W_{\log_2 n - 1}(X + Y)}{W_{\log_2 n - 1}(\omega_{2^{\log_2 n - 1}})} d_{m + 2^{\log_2 n - 1}}

Using Lemma 1:

Wlog2n1(X+Y)=Wlog2n1(X)+Wlog2n1(Y)W_{\log_2 n - 1}(X + Y) = W_{\log_2 n - 1}(X) + W_{\log_2 n - 1}(Y)

Since Y{ωb}b=02i1Y \in \{\omega_b\}_{b=0}^{2^i - 1}, we know Wlog2n1(Y)=0W_{\log_2 n - 1}(Y) = 0, so:

Δlog2n1m(X+Y)=dm+Wlog2n1(X)Wlog2n1(ω2log2n1)dm+2log2n1=Δlog2n1m(X)\begin{align*} \Delta^m_{\log_2 n - 1}(X + Y) &= d_m + \frac{W_{\log_2 n - 1}(X)}{W_{\log_2 n - 1}(\omega_{2^{\log_2 n - 1}})} d_{m + 2^{\log_2 n - 1}} \\ &= \Delta^m_{\log_2 n -1}(X) \end{align*}

Case 3: Inductive Step

Assume the equality holds for i=c+1i = c+ 1. At , we have:

Δcm(X+Y)=Δc+1m(X+Y)+Wc(X+Y)Wc(ω2c)Δc+1m+2c(X+Y)\Delta^m_{c}(X + Y) = \Delta^m_{c + 1}(X + Y) + \frac{W_{c}(X + Y)}{W_{c}(\omega_{2^c})} \Delta^{m + 2^c}_{c + 1}(X + Y)

By Lemma 1:

Wc(X+Y)=Wc(X)+Wc(Y)W_c(X + Y) = W_c(X) + W_c(Y)

Since Y{ωb}b=02c1Y \in \{\omega_b\}_{b=0}^{2^c - 1}, we know Wc(Y)=0W_{c}(Y) = 0, thus:

Δcm(X+Y)=Δc+1m(X+Y)+Wc(X)Wc(ω2c)Δc+1m+2c(X+Y)=Δcm(X)\begin{align*} \Delta^m_{c}(X + Y) &= \Delta^m_{c + 1}(X + Y) + \frac{W_{c}(X)}{W_{c}(\omega_{2^c})} \Delta^{m + 2^c}_{c + 1}(X + Y) \\ &= \Delta^m_c(X) \end{align*}

Transform

Define the transform Ψ\Psi as:

Ψ(i,m,l)={{Δim(ωc+ωl)c{b2i}b=0n/2i1} if 0i<log2n{dm} if i=log2n\Psi(i, m, l) = \begin{cases} \{ \Delta^m_i(\omega_c + \omega_l)| c \in \{b \cdot 2^i\}^{n/2^i - 1}_{b = 0} \} & \text{ if } 0 \le i < \log_2 n \\ \{d_m\} & \text{ if } i = \log_2n \end{cases}

where 0m<2i0 \le m < 2^i.

The transform computes {Ψ(log2n,k,l)k[0,n1]}Ψ(0,0,l)\{\Psi(\log_2 n, k, l)|k \in [0, n-1]\} \rightarrow \Psi(0, 0, l). For n=8n = 8, this becomes:

{d0,d1,d2,d7}=Ψ(3,0,l)Ψ(3,1,l)Ψ(3,2,l)Ψ(3,7,l){Δ00(ω0+ωl),Δ00(ω1+ωl),Δ00(ω2+ωl),,Δ00(ω7+ωl)}=Ψ(0,0,l)\{d_0, d_1, d_2 \dots, d_{7}\} = \Psi(3, 0, l) \cup \Psi(3, 1, l) \cup \Psi(3, 2, l) \cup \cdots \cup \Psi(3, 7, l) \\ \rightarrow \{\Delta^0_0(\omega_0 + \omega_l),\Delta^0_0(\omega_1 + \omega_l), \Delta^0_0(\omega_2 + \omega_l), \dots, \Delta^0_0(\omega_{7} + \omega_l)\} = \Psi(0, 0, l)

Remember that Δ00(X)\Delta^0_0(X) is equivalent to [Dn](X)[D_n](X).

Ψ(i,m,l)\Psi(i, m, l) can be divided into two parts as follows:

  • {Δim(ωc+ωl)c{b2i+1}b=0n/2i+11}\{\Delta^m_i(\omega_c + \omega_l)| c \in \{b \cdot 2^{i+1}\}^{n/2^{i+1} - 1}_{b = 0}\} which can be computed from Ψ(i+1,m,l)\Psi(i + 1, m, l).

  • {Δim(ωc+ωl+ω2i)c{b2i+1}b=0n/2i+11}\{\Delta^m_i(\omega_c + \omega_l + \omega_{2^i})| c \in \{b \cdot 2^{i+1}\}^{n/2^{i+1} - 1}_{b = 0}\} which can be computed from Ψ(i+1,m+2i,l)\Psi(i + 1, m +2^i, l).

Part 1. Ψ(i+1,m,l)\Psi(i + 1, m, l)

Δim(ωc+ωl)=Δi+1m(ωc+ωl)+Wi(ωc+ωl)Wi(ω2i)Δi+1m+2i(ωc+ωl)\Delta^m_i(\omega_c + \omega_l) = \Delta^m_{i+1}(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l)}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l)

Since all the right-hand terms are known, the left-hand terms can be determined.

Part 2. Ψ(i+1,m+2i,l)\Psi(i + 1, m + 2^i, l)

Δim(ωc+ωl+ω2i)=Δi+1m(ωc+ωl+ω2i)+Wi(ωc+ωl+ω2i)Wi(ω2i)Δi+1m+2i(ωc+ωl+ω2i)=Δi+1m(ωc+ωl)+Wi(ωc+ωl+ω2i)Wi(ω2i)Δi+1m+2i(ωc+ωl)Lemma 2.=Δi+1m(ωc+ωl)+Wi(ωc+ωl)+Wi(ω2i)Wi(ω2i)Δi+1m+2i(ωc+ωl)Lemma 1.=Δi+1m(ωc+ωl)+Wi(ωc+ωl)Wi(ω2i)Δi+1m+2i(ωc+ωl)+Δi+1m+2i(ωc+ωl)=Δim(ωc+ωl)+Δi+1m+2i(ωc+ωl)\begin{align*} \Delta^m_i(\omega_c + \omega_l + \omega_{2^i}) &= \Delta^m_{i+1}(\omega_c + \omega_l + \omega_{2^i}) + \frac{W_i(\omega_c + \omega_l + \omega_{2^i})}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l + \omega{2^i}) \\ &= \Delta^m_{i+1}(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l + \omega_{2^i})}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l) \because \text{Lemma } 2. \\ &= \Delta^m_{i+1}(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l) + W_i(\omega_{2^i})}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l) \because \text{Lemma } 1. \\ &= \Delta^m_{i+1}(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l)}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l) + \Delta^{m + 2^i}_{i +1}(\omega_c + \omega_l) \\ &= \Delta^m_i(\omega_c + \omega_l) + \Delta^{m + 2^i}_{i+1}(\omega_c + \omega_l) \end{align*}

Since Δim(ωc+ωl)\Delta^m_i(\omega_c + \omega_l) can be computed from the Part 1, the left-hand terms can be determined.

When n=8,i=2n=8, i=2, for Ψ(2,m,l)\Psi(2, m, l), it can be split into Ψ(3,m,l)={dm}\Psi(3,m , l) = \{d_m\} and Ψ(3,m+4,l)=Δ3m+4(X)={dm+4}\Psi(3, m + 4, l) = \Delta^{m+4}_3(X) =\{d_{m+4}\}.

Ψ(2,m,l)={Δ2m(ω0+ωl),Δ2m(ω4+ωl)}={Δ3m(ω0+ωl)+W2(ω0+ωl)W2(ω4)Δ3m+4(ω0+ωl),Δ3m(ω4+ωl)+W2(ω4+ωl)W2(ω4)Δ3m+4(ω4+ωl)}={dm+W2(ω0+ωl)W2(ω4)dm+4,dm+W2(ω4+ωl)W2(ω4)dm+4}\begin{align*} \Psi(2, m, l) &= \{\Delta^m_2(\omega_0 + \omega_l),\Delta^m_2(\omega_4 + \omega_l)\} \\ &= \{\Delta^m_3(\omega_0 + \omega_l) + \frac{W_2(\omega_0 + \omega_l)}{W_2(\omega_4)}\Delta^{m + 4}_3(\omega_0 + \omega_l), \Delta^m_3(\omega_4 + \omega_l) + \frac{W_2(\omega_4 + \omega_l)}{W_2(\omega_4)}\Delta^{m + 4}_3(\omega_4 + \omega_l) \} \\ &= \{d_m + \frac{W_2(\omega_0 + \omega_l)}{W_2(\omega_4)}d_{m+4}, d_m + \frac{W_2(\omega_4 + \omega_l)}{W_2(\omega_4)}d_{m+4} \} \end{align*}

When n=8,i=1n=8, i=1, for Ψ(1,m,l)\Psi(1, m, l), it can be split intoΨ(2,m,l)={Δ2m(ω0+ωl),Δ2m(ω4+ωl)}\Psi(2, m, l) = \{\Delta^m_2(\omega_0 + \omega_l), \Delta^m_2(\omega_4 + \omega_l)\} and Ψ(2,m+2,l)={Δ2m+2(ω0+ωl),Δ2m+2(ω4+ωl)}\Psi(2, m + 2, l) = \{\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^{m + 2}_2(\omega_4 + \omega_l)\}.

Ψ(1,m,l)={Δ1m(ω0+ωl),Δ1m(ω2+ωl),Δ1m(ω4+ωl),Δ1m(ω6+ωl)}={Δ2m(ω0+ωl)+W1(ω0+ωl)W1(ω2)Δ2m+2(ω0+ωl),Δ2m(ω2+ωl)+W1(ω2+ωl)W1(ω2)Δ2m+2(ω2+ωl),Δ2m(ω4+ωl)+W1(ω4+ωl)W1(ω2)Δ2m+2(ω4+ωl),Δ2m(ω6+ωl)+W1(ω6+ωl)W1(ω2)Δ2m+2(ω6+ωl)}={Δ2m(ω0+ωl)+W1(ω0+ωl)W1(ω2)Δ2m+2(ω0+ωl),Δ2m(ω0+ωl+ω2)+W1(ω0+ωl+ω2)W1(ω2)Δ2m+2(ω0+ωl+ω2),Δ2m(ω4+ωl)+W1(ω4+ωl)W1(ω2)Δ2m+2(ω4+ωl),Δ2m(ω4+ωl+ω2)+W1(ω4+ωl+ω2)W1(ω2)Δ2m+2(ω4+ωl+ω2)}={Δ2m(ω0+ωl)+W1(ω0+ωl)W1(ω2)Δ2m+2(ω0+ωl),Δ2m(ω0+ωl)+W1(ω0+ωl)W1(ω2)Δ2m+2(ω0+ωl),Δ2m(ω4+ωl)+W1(ω4+ωl)W1(ω2)Δ2m+2(ω4+ωl),Δ2m(ω4+ωl)+W1(ω4+ωl)W1(ω2)Δ2m+2(ω4+ωl)}\begin{align*}\Psi(1, m, l) &= \{\Delta^m_1(\omega_0 + \omega_l),\Delta^m_1(\omega_2 + \omega_l),\Delta^m_1(\omega_4 + \omega_l),\Delta^m_1(\omega_6 + \omega_l)\} \\ &= \{\Delta^m_2(\omega_0 + \omega_l) + \frac{W_1(\omega_0 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^m_2(\omega_2 + \omega_l) + \frac{W_1(\omega_2 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_2 + \omega_l), \Delta^m_2(\omega_4 + \omega_l) + \frac{W_1(\omega_4 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l), \Delta^m_2(\omega_6 + \omega_l) + \frac{W_1(\omega_6 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_6 + \omega_l) \} \\ &= \{\Delta^m_2(\omega_0 + \omega_l) + \frac{W_1(\omega_0 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^m_2(\omega_0 + \omega_l + \omega_2) + \frac{W_1(\omega_0 + \omega_l + \omega_2)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l + \omega_2), \Delta^m_2(\omega_4 + \omega_l) + \frac{W_1(\omega_4 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l), \Delta^m_2(\omega_4 + \omega_l + \omega_2) + \frac{W_1(\omega_4 + \omega_l + \omega_2)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l + \omega_2) \} \\ &= \{\Delta^m_2(\omega_0 + \omega_l) + \frac{W_1(\omega_0 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^m_2(\omega_0 + \omega_l) + \frac{W_1(\omega_0 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_0 + \omega_l), \Delta^m_2(\omega_4 + \omega_l) + \frac{W_1(\omega_4 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l), \Delta^m_2(\omega_4 + \omega_l) + \frac{W_1(\omega_4 + \omega_l)}{W_1(\omega_2)}\Delta^{m + 2}_2(\omega_4 + \omega_l) \} \\ \end{align*}

Inverse Transform

To compute Ψ(i+1,m,l)\Psi(i + 1, m, l) and Ψ(i+1,m+2i,l)\Psi(i + 1, m + 2^i, l) from Ψ(i,m,l)\Psi(i, m, l):

Part 1. Ψ(i+1,m+2i,l)\Psi(i + 1, m + 2^i, l)

Ψ(i+1,m+2i,l)={Δi+1m+2i(ωc+ωl)c{b2i+1}b=0n/2i+11}\Psi(i + 1, m + 2^i, l) = \{\Delta^{m + 2^i}_{i+1}(\omega_c + \omega_l)| c \in \{b \cdot 2^{i+1}\}^{n/2^{i+1} - 1}_{b = 0}\}

where: (Refer to Part 2. in Transform section above.)

Δi+1m+2i(ωc+ωl)=Δim(ωc+ωl)+Δim(ωc+ωl+ω2i)\Delta^{m + 2^i}_{i+1}(\omega_c + \omega_l) = \Delta^m_i(\omega_c + \omega_l) + \Delta^m_i(\omega_c + \omega_l + \omega_{2^i})

Since all the right-hand terms are known, the left-hand terms can be determined.

Part 2. Ψ(i+1,m,l)\Psi(i + 1, m, l)

Ψ(i+1,m,l)={Δi+1m(ωc+ωl)c{b2i+1}b=0n/2i+11}\Psi(i + 1, m, l) = \{\Delta^{m }_{i+1}(\omega_c + \omega_l)| c \in \{b \cdot 2^{i+1}\}^{n/2^{i+1} - 1}_{b = 0}\}

where (Refer to Part 1. in Transform section above):

Δi+1m(ωc+ωl)=Δim(ωc+ωl)+Wi(ωc+ωl)Wi(ω2i)Δi+1m+2i(ωc+ωl)\Delta^{m}_{i+1}(\omega_c + \omega_l) = \Delta^m_i(\omega_c + \omega_l) + \frac{W_i(\omega_c + \omega_l)}{W_i(\omega_{2^i})}\Delta^{m + 2^i}_{i+1}(\omega_c + \omega_l)

Since Δim(ωc+ωl)\Delta^m_i(\omega_c + \omega_l) can be computed from the Part 1, the left-hand terms can be determined.

The diagram above illustrates the data dependencies for transforming and inversely transforming a polynomial of size 8. Each elemetter represents scalar multiplication by W^ij\widehat{W}^j_i.

W^ij=Wi(ωj)Wi(ω2i)\widehat{W}^j_i = \frac{W_i(\omega_j)}{W_i(\omega_{2^i})}

Conclusion

The method for performing a formal derivative on the Novel Polynomial Basis and its use in the RS erasure decoding algorithm is omitted here due to space constraints. For those interested, please refer to the original paper.

Complexities of Previous n-point FFT Algorithms

Using the newly proposed Novel Polynomial Basis, the Additive NTT achieves O(nlogn)O(n \log n) additive complexity and O(nlogn)O(n \log n) multiplicative complexity without any constraints. Consequently, for the first time, RS-encoding over characteristic-2 finite fields achieves O(nlogn)O(n \log n) complexity.

Additionally, it is well-known that polynomial multiplication can be optimized using FFT. Similarly, by leveraging the Novel Polynomial Basis, multiplication in characteristic-2 finite fields can also be optimized.

Written by ryan Kim from A41

Last updated