Number Theoretic Transform

Presentation: https://youtu.be/jeHQtLduHN8

Preliminaries

Discrete Linear Convolution

Convolution is a mathematical operation that blends two functions (or signals) to produce a third function, which shows how one function modifies or overlaps with the other.

A convolution is linear if it satisfies the properties of additivity and homogeneity. This means that the convolution of a linear combination of sequences is the same as the corresponding linear combination of their convolutions. For example, (A+B)C=AC+BC(A+B)\circ C= A\circ C + B\circ C

So discrete linear convolution is when it is working on sequences of integers rather than on continuous functions.

Polynomial Multiplication

Definition 1: Suppose that G(x)G(x) and H(x)H(x) are polynomials of degree n1n − 1 in the ring Zq[x]\mathbb{Z}_q[x] where qZq \in \mathbb{Z} and xx is the polynomial variable, a polynomial multiplication of G(x)G(x) and H(x)H(x) is defined as:

Y(x)=G(x)H(x)=k=02(n1)ykxk(1)Y(x)=G(x)\cdot H(x)=\sum_{k=0}^{2(n-1)}y_k x^k \tag{1}

where yk=i=0kgihkimodqy_k=\sum_{i=0}^{k}g_i h_{k-i} \mod q, g\bm{g} and h\bm{h} are the polynomial coefficients of G(x)G(x) and H(x)H(x) respectively.

Polynomial multiplication is equivalent to a discrete linear convolution between the coefficients' vectors g=(g0,,gn)\bm{g}=(g_0,\dots,g_n) and h=(h0,,hn)\bm{h}=(h_0,\dots,h_n).

Cyclic Convolution

Definition 2: Suppose that G(x)G(x) and H(x)H(x) are polynomials of degree n1n − 1 in the quotient ring Zq[x]/(xn1)\mathbb{Z}_q[x]/(x^n − 1) where qZq\in\mathbb{Z}. A cyclic convolution or positive wrapped convolution (PWC) is defined as:

PWC(x)=k=0n1ckxk(2)\mathsf{PWC}(x)=\sum^{n-1}_{k=0}c_kx^k\tag{2}

where ck=i=0kgihki+i=k+1n1gihk+nimodqc_k=\sum^{k}_{i=0}g_i h_{k-i} + \sum^{n-1}_{i=k+1}g_i h_{k+n-i} \mod q. If Y(x)Y(x) from equation (1)(1) is the result of their linear convolution in the ring Zq[x]\mathbb{Z}_q[x], it can also be defined as:

PWC(x)=Y(x)mod(xn1)(3)\mathsf{PWC}(x)=Y(x) \mod (x^n-1) \tag{3}

Naive method to calculate the PWC\mathsf{PWC} is through a polynomial multiplication followed by a long division. This method has O(n2)O(n^2) complexity.

The term "cyclic" stems from the fact that xnx^n cycles back to 11 in this quotient ring. For example, F(x)=xnF(x)=x^n will map to F(x)=1F(x)=1 in this quotient ring.

Negacyclic convolution

Definition 3: Suppose that G(x)G(x) and H(x)H(x) are polynomials of degree n1n − 1 in the quotient ring Z[x]/(xn+1)\mathbb{Z}[x]/(x^n + 1) where qZq \in \mathbb{Z}. A negacyclic convolution or negative wrapped convolution, NWC(x)\mathsf{NWC}(x) is defined as:

NWC(x)=k=0n1ckxk(4)\mathsf{NWC}(x)=\sum_{k=0}^{n-1}c_k x^k \tag{4}

where ck=i=0kgihkii=k+in1gihk+nimodqc_k=\sum_{i=0}^k g_i h_{k-i} - \sum_{i=k+i}^{n-1}g_i h_{k+n-i}\mod q. If Y(x)Y(x) from equation (1)(1) is the result of their linear convolution in the ring Z[x]\mathbb{Z}[x], it also can be defined as:

NWC(x)=Y(x)mod(xn+1)(5)\mathsf{NWC}(x)=Y(x) \mod (x^n + 1) \tag{5}

Note that the only difference between cyclic and negacyclic convolution is the divisor.

The term "negacyclic" stems from the fact that xnx^n cycles back to 1-1 in this quotient ring. For example, F(x)=xnF(x)=x^n will map to F(x)=1F(x)=-1 in this quotient ring.

Number Theoretic Transform

Many researchers do not differentiate the term NTT and FFT-based algorithms to calculate NTT, which creates confusion when understanding the topic. This report refers to the transformation itself as NTT and the FFT-like algorithms as fast-NTT

The classical NTT has quadratic complexity of O(n2)O(n^2) while fast-NTT algorithms have a more efficient quasi-linear complexity O(nlogn).O(n\log n).

Remember that for NTT, we are particularly interested in the evaluations at the roots of the quotient polynomial. (AB=C+QuotientPolycA\cdot B= C + \mathsf{QuotientPoly} \cdot c and we want the QuotientPoly\mathsf{QuotientPoly} to vanish).

Definition 4: Let Zq\mathbb{Z}_q be an integer ring modulo qq, and n1n − 1 is the polynomial degree of G(x)G(x) and H(x)H(x). Such rings have a multiplicative identity (unity) of 1. Define ω\omega as primitive nn-th root of unity in Zq\mathbb{Z}_q if and only if:

ωn1modq(6)\omega^n\equiv 1 \mod q \tag{6}

and

ωk≢1modq(7)\omega^k\not\equiv 1\mod q\tag{7}

for all k=1,,n1k=1,\dots,n-1.

One thing to note is that the primitive nn-th root of unity in a ring Zq\mathbb{Z}_q might not be unique. For example, in a ring Z7\mathbb{Z}_{7}, primitive 3rd root of unity can be 22 and 44. The choice of value of ω\omega will be important in calculating NWC\mathsf{NWC} and PWC\mathsf{PWC}.

Definition 5: The Number Theoretic Transform (NTT) of a vector of polynomial coefficients a\boldsymbol{a} is defined as a^=NTT(a)\hat{\boldsymbol{a}} = \mathsf{NTT}(\boldsymbol{a}), where:

a^j=i=0n1ωijaimodq(8)\hat{a}_j=\sum^{n-1}_{i=0}\omega^{ij}a_i\mod q \tag{8}

and j=0,1,,n1j=0,1,\dots,n-1. Here, a^\hat{\bm{a}} denotes the evaluations of the polynomial defined by a\bm{a} over {ω0,ω1,,ωn1}\{\omega^{0},\omega^{1},\dots,\omega^{n-1}\} which are the roots of (xn1)(x^n-1).

Definition 6: The Inverse of Number Theoretic Transform (INTT) of an NTT vector a^\hat{\boldsymbol{a}} is defined as a=INTT(a^)\boldsymbol{a} = \mathsf{INTT}(\hat{\boldsymbol{a}}), where:

ai=n1j=0n1wija^jmodq(9)a_i=n^{-1}\sum^{n-1}_{j=0}w^{-ij}\hat{a}_j \mod q\tag{9}

and j=0,1,,n1j=0,1,\dots,n-1.

Note that the INTT has a very similar formula to NTT. The only differences are ω\omega replaced by its inverse in Zq\mathbb{Z}_q and a n1n^{−1} scaling factor. It always holds that a=INTT(NTT(a))\bm{a} = \mathsf{INTT}(\mathsf{NTT}(\bm{a})).

In the ZK scene, it is common to work on a polynomial with some max degree n1n-1. This just means that we are working on polynomials from the quotient ring Zq[x]/(xn1)\mathbb{Z}_q[x]/(x^n − 1). In such rings, we must utilize positive-wrapped convolution.

In the context of PQC and HE, the chosen ring is mostly Zq[x]/(xn+1)\mathbb{Z}_q[x]/(x^n + 1) instead of Zq[x]/(xn1)\mathbb{Z}_q[x]/(x^n − 1). One must calculate the polynomial multiplications via the negative-wrapped convolution in such rings. To calculate negative-wrapped convolution, one needs the primitive 2n2n-th root of unity, ψ\psi.

Definition 7: Let Zq\mathbb{Z}_q be an integer ring modulo qq, and n1n - 1 is the polynomial degree of G(x)G(x) and H(x)H(x) and ω\omega is its primitive nn-th root of unity. Define ψ\psi as the primitive 2n2n-th root of unity if and only if:

(ψ2ωmodq)(ψn1modq)(10)(\psi^2\equiv\omega\mod q)\land (\psi^n \equiv -1 \mod q) \tag{10}

Example. In a ring Z7681\mathbb{Z}_{7681} and n=4n = 4, when ω=3383\omega = 3383, the value of ψ\psi can be 1925 or 5756 as 19252575623383mod76811925^2 \equiv 5756^2 \equiv 3383 \mod 7681 and 192545756476801mod76811925^4 \equiv 5756^4 \equiv 7680 \equiv −1 \mod 7681. Therefore, one can choose the value of ψ=1925\psi = 1925 or ψ=5756\psi = 5756.

Definition 8: The Negative-Wrapped Number Theoretic Transform (NTTψ\mathsf{NTT}^\psi) of a vector of polynomial coefficients a\bm{a} is defined as a^=NTTψ(a)\hat{\boldsymbol{a}} = \mathsf{NTT^\psi}(\boldsymbol{a}), where:

a^j=i=0n1ψ2ij+iaimodq(11)\hat{a}_j = \sum^{n−1}_{i=0} \psi^{2ij+i}a_i \mod q \tag{11}

and j=0,1,,n1j=0,1,\dots,n-1. Here, a^\hat{\bm{a}} denotes the evaluations of the polynomial defined by a\bm{a} over {ψ1,ψ3,,ψ2n1}\{\psi^{1},\psi^{3},\dots,\psi^{2n-1}\} which are the roots of (xn+1)(x^n+1).

Definition 9: The Negative-Wrapped Inverse of Number Theoretic Transform (INTT) of an NTT vector a^\hat{\bm{a}} is defined as a=INTTψ1(a^)\bm{a} = \mathsf{INTT}^{\psi^{-1}}(\hat{\bm{a}}), where:

ai=n1j=0n1ψiωija^jmodq(12)a_i=n^{-1}\sum_{j=0}^{n-1}\psi^{-i}\omega^{-ij}\hat{a}_j \mod q \tag{12}

and i=0,1,,n1i=0,1,\dots,n-1. Substituting ω=ψ2\omega = \psi^2 yields:

ai=n1j=0n1ψ(2ij+i)a^jmodq(17)a_i=n^{-1}\sum^{n-1}_{j=0}\psi^{-(2ij+i)}\hat{a}_j\mod q \tag{17}

To reduce the complexity and fasten the process of the matrix multiplication needed for the NTT transformation, one can use ‘‘divide and conquer’’ techniques by utilizing the periodicity and symmetry property of:

periodicity:   ψk+2n=ψksymmetry:   ψk+n=ψk(18)\begin{aligned}\text{periodicity:}\ \ \ &\psi^{k+2n}& &=&\psi^k \\ \text{symmetry:}\ \ \ &\psi^{k+n}& &=&-\psi^k\end{aligned} \tag{18}

Cooley-Tukey (CT) Algorithm for Fast NTT

PWC case

From equation (8) for NTT\mathsf{NTT}, one can separate the summation into two parts, based on odd and even indices:

a^j=i=0n1ωijaimodq=i=0n/21ω2ija2i+i=0n/21ω2ij+ja2i+1modq=i=0n/21ω2ija2i+ωji=0n/21ω2ija2i+1modq(19)\begin{aligned} \hat{a}_j& = \sum_{i=0}^{n-1}\omega^{ij}a_i\mod q \\ &=\sum_{i=0}^{n/2-1}\omega^{2ij}a_{2i} + \sum_{i=0}^{n/2-1}\omega^{2ij + j}a_{2i+1}\mod q\\ &=\sum_{i=0}^{n/2-1}\omega^{2ij}a_{2i} + \omega^{j}\sum_{i=0}^{n/2-1}\omega^{2ij}a_{2i+1}\mod q \end{aligned}\tag{19}

Similarly, we can get the equation for a^j+n2\hat{\bm{a}}_{j+\frac{n}{2}} by using the fact that ωn21modq\omega^{\frac{n}{2}}\equiv-1 \mod q :

a^j+n2=i=0n1ωi(j+n2)aimodq=i=0n/21ω2i(j+n2)a2i+i=0n/21ω(2i+1)(j+n2)a2i+1modq=i=0n/21ω2ij+nia2i+i=0n/21ω2ij+j+ni+n2a2i+1modq=i=0n/21ω2ija2i+ωj+n2i=0n/21ω2ija2i+1modq=i=0n/21ω2ija2iωji=0n/21ω2ija2i+1modq(20)\begin{aligned} \hat{a}_{j+\frac{n}{2}}& = \sum_{i=0}^{n-1}\omega^{i(j+\frac{n}{2})}a_i &\mod q \\ &=\sum_{i=0}^{n/2-1}\omega^{2i(j+\frac{n}{2})}a_{2i} + \sum_{i=0}^{n/2-1}\omega^{(2i+1)(j + \frac{n}{2})}a_{2i+1} &\mod q\\ &=\sum_{i=0}^{n/2-1}\omega^{2ij + {ni}}a_{2i} + \sum_{i=0}^{n/2-1}\omega^{2ij + j + ni + \frac{n}{2}}a_{2i+1} &\mod q \\ &=\sum_{i=0}^{n/2-1}\omega^{2ij}a_{2i} + \omega^{j+\frac{n}{2}}\sum_{i=0}^{n/2-1}\omega^{2ij}a_{2i+1} &\mod q \\ &=\sum_{i=0}^{n/2-1}\omega^{2ij}a_{2i} - \omega^{j}\sum_{i=0}^{n/2-1}\omega^{2ij}a_{2i+1} &\mod q\end{aligned}\tag{20}

If we denote, Aj=i=0n/21ω2ija2iA_j=\sum^{n/2-1}_{i=0}\omega^{2ij}a_{2i} and Bj=i=0n/21ω2ija2i+1B_j=\sum^{n/2-1}_{i=0}\omega^{2ij}a_{2i+1}, the equation (19)(19) and (20)(20) becomes:

a^j=Aj+ωjBjmodqa^j+n/2=AjωjBjmodq(21)\begin{aligned}\hat{\boldsymbol{a}}_j&=A_j + \omega^j B_j \mod q\\\hat{\boldsymbol{a}}_{j+n/2}&=A_j-\omega^jB_j \mod q \end{aligned}\tag{21}

With this finding, we can calculate AjA_j and BjB_j for j=0,,n2j=0,\dots,\frac{n}{2} and calculate a^\hat{\bm{a}} by reusing them for the upper half. Notice that AjA_j and BjB_j can be calculated using n2\frac{n}{2} point NTT so if we repeat recursively, we can achieve the best case scenario O(nlogn)O(n\log n) which occurs when nn is a power of 2.

Example. Let's consider the case when a=(1,2,3,4)\bm{a}=(1,2,3,4).

a^=[ω0ω0ω0ω0ω0ω1ω2ω3ω0ω2ω4ω6ω0ω3ω6ω9][1234]\hat{\bm{a}}= \begin{bmatrix} \omega^{0} & \omega^{0} & \omega^{0} & \omega^{0} \\ \omega^{0} & \omega^{1} & \omega^{2} & \omega^{3} \\ \omega^{0} & \omega^{2} & \omega^{4} & \omega^{6} \\ \omega^{0} & \omega^{3} & \omega^{6} & \omega^{9} \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ \end{bmatrix}
a^=[ω0ω0ω0ω0ω0ω1ω2ω3ω0ω2ω0ω2ω0ω3ω2ω1][1234]\hat{\bm{a}}= \begin{bmatrix} \omega^{0} & \omega^{0} & \omega^{0} & \omega^{0} \\ \omega^{0} & \omega^{1} & \omega^{2} & \omega^{3} \\ \omega^{0} & \omega^{2} & \omega^{0} & \omega^{2} \\ \omega^{0} & \omega^{3} & \omega^{2} & \omega^{1} \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ \end{bmatrix}
a^0=ω01+ω02+ω03+ω04a^1=ω01+ω12+ω23+ω34a^2=ω01+ω22+ω03+ω24a^3=ω01+ω32+ω23+ω14\hat{a}_0=\omega^0\cdot 1 + \omega^0\cdot 2 + \omega^0\cdot 3 + \omega^0\cdot 4 \\ \hat{a}_1=\omega^0\cdot 1 + \omega^1\cdot 2 + \omega^2\cdot 3 + \omega^3\cdot 4 \\ \hat{a}_2=\omega^0\cdot 1 + \omega^2\cdot 2 + \omega^0\cdot 3 + \omega^2\cdot 4 \\ \hat{a}_3=\omega^0\cdot 1 + \omega^3\cdot 2 + \omega^2\cdot 3 + \omega^1\cdot 4
a^0=ω0(1+3)+ω0(2+4)a^1=ω0(13)+ω1(24)a^2=ω0(1+3)ω0(2+4)a^3=ω0(13)ω1(24)\hat{a}_0=\omega^0\cdot (1 + 3) + \omega^0\cdot (2 + 4) \\ \hat{a}_1=\omega^0\cdot (1 - 3) + \omega^1\cdot (2 - 4) \\ \hat{a}_2=\omega^0\cdot (1 + 3) -\omega^0\cdot (2 + 4) \\ \hat{a}_3=\omega^0\cdot (1 - 3) - \omega^1\cdot (2 - 4)

The idea is to calculate similar terms in the brackets once and then distribute the results instead of calculating them multiple times.

NWC case

From equation (11)(11) for NTTψ\mathsf{NTT}^\psi, one can separate the summation into two parts similarly into following:

a^j=i=0n1ψ2ij+iaimodq=i=0n/21ψ4ij+2ia2i+i=0n/21ψ4ij+2j+2i+1aa2i+1modq=i=0n/21ψ4ij+2ia2i+ψ2j+1i=0n/21ψ4ij+2iaa2i+1modq(22)\begin{aligned}\hat{\boldsymbol{a}}_j& = \sum_{i=0}^{n-1}\psi^{2ij+i}\boldsymbol{a}_i\mod q \\ & = \sum_{i=0}^{n/2-1}\psi^{4ij+2i}\boldsymbol{a}_{2i} + \sum_{i=0}^{n/2-1}\psi^{4ij + 2j + 2i + 1}\boldsymbol{a}_{a_{2i+1}}&\mod q\\ &=\sum_{i=0}^{n/2-1}\psi^{4ij+2i}\boldsymbol{a}_{2i} + \psi^{2j+1}\sum_{i=0}^{n/2-1}\psi^{4ij + 2i}\boldsymbol{a}_{a_{2i+1}}&\mod q\end{aligned}\tag{22}

Based on the ψ\psi's symmetry properties:

a^j+n/2=i=0n/21ψ4ij+2ia2iψ2j+1i=0n/21ψ4ij+2iaa2i+1modq(23)\hat{\boldsymbol{a}}_{j+n/2}=\sum_{i=0}^{n/2-1}\psi^{4ij+2i}\boldsymbol{a}_{2i} - \psi^{2j + 1}\sum_{i=0}^{n/2-1}\psi^{4ij + 2i}\boldsymbol{a}_{a_{2i+1}}\mod q \tag{23}

Let Aj=i=0n/21ψ4ij+2ia2iA_j=\sum^{n/2-1}_{i=0}\psi^{4ij + 2i}a_{2i} and Bj=i=0n/21ψ4ij+2ia2i+1B_j=\sum^{n/2-1}_{i=0}\psi^{4ij+2i}a_{2i+1}, equations (22)(22) and (23)(23) become:

a^j=Aj+ψ2j+1Bjmodqa^j+n/2=Ajψ2j+1Bjmodq(24)\begin{aligned}\hat{\boldsymbol{a}}_j &= A_j + \psi^{2j+1}B_j\mod q\\ \hat{\boldsymbol{a}}_{j+n/2}&=A_j-\psi^{2j+1}B_j\mod q\end{aligned}\tag{24}

With this finding, we can calculate AjA_j and BjB_j for j=0,,n2j=0,\dots,\frac{n}{2} and calculate a^\hat{\bm{a}} by reusing them for the upper half. Notice that AjA_j and BjB_j can be calculated using n2\frac{n}{2} point NTT so if we repeat recursively, we can achieve the best case scenario O(nlogn)O(n\log n) which occurs when nn is a power of 2.

Figure 1. Cooley-Tukey Butterfly graph notation

Figure 1 illustrates how this butterfly operation is denoted as a graph. This figure represents the computation of A+ψkBA+\psi^kB and AψkBA-\psi^k B.

Gentleman-Sande (GS) Algorithm for Fast INTT

PWC case

For the INTT, instead of dividing the summation by even and odd indices, it is separated by the lower and upper half of the summation. From equation (10)(10) for INTT\mathsf{INTT} and ignoring n1n^{-1} term:

ai=j=0n1ωija^jmodq=j=0n21ωija^j+j=0n21ωi(j+n2)a^j+n2modq=j=0n21ωija^j+ωni2j=0n21ωija^j+n2modq=j=0n21(a^j+ωni2a^j+n2)ωijmodq(25)\begin{aligned} a_i&=\sum^{n-1}_{j=0}\omega^{-ij}\hat{a}_j &\mod q \\ &=\sum^{\frac{n}{2}-1}_{j=0}\omega^{-ij}\hat{a}_j+\sum^{\frac{n}{2}-1}_{j=0}\omega^{-i(j+\frac{n}{2})}\hat{a}_{j+\frac{n}{2}} &\mod q\\ &=\sum^{\frac{n}{2}-1}_{j=0}\omega^{-ij}\hat{a}_j+\omega^{-\frac{ni}{2}}\sum^{\frac{n}{2}-1}_{j=0}\omega^{-ij}\hat{a}_{j+\frac{n}{2}} &\mod q \\ &=\sum^{\frac{n}{2}-1}_{j=0}(\hat{a}_j+\omega^{-\frac{ni}{2}}\hat{a}_{j+\frac{n}{2}})\cdot\omega^{-ij} &\mod q \end{aligned}\tag{25}

If we consider the odd and even term separately, we get:

a2i=j=0n21(a^j+ωnia^j+n2)ω2ijmodq=j=0n21(a^j+a^j+n2)ω2ijmodq(26)\begin{align*} a_{2i}&=\sum^{\frac{n}{2}-1}_{j=0}(\hat{a}_j+\omega^{-ni}\hat{a}_{j+\frac{n}{2}})\cdot\omega^{-2ij} &\mod q \\ &=\sum^{\frac{n}{2}-1}_{j=0}(\hat{a}_j+\hat{a}_{j+\frac{n}{2}})\cdot\omega^{-2ij} &\mod q \end{align*} \tag{26}
a2i+1=j=0n21(a^j+ωnin2a^j+n2)ω2ijjmodq=j=0n21((a^ja^j+n2)ωj)ω2ijmodq(27)\begin{aligned} a_{2i+1}&=\sum^{\frac{n}{2}-1}_{j=0}(\hat{a}_j+\omega^{-ni-\frac{n}{2}}\hat{a}_{j+\frac{n}{2}})\cdot\omega^{-2ij -j} &\mod q \\ &=\sum^{\frac{n}{2}-1}_{j=0}((\hat{a}_j-\hat{a}_{j+\frac{n}{2}})\cdot\omega^{-j})\cdot\omega^{-2ij} &\mod q \end{aligned} \tag{27}

Let Ai=j=0n21(a^j+a^j+n2)ω2ijA_{i}=\sum^{\frac{n}{2}-1}_{j=0}(\hat{a}_j+\hat{a}_{j+\frac{n}{2}})\omega^{-2ij} and Bi=j=0n21((a^ja^j+n2)ωj)ω2ijB_{i}=\sum^{\frac{n}{2}-1}_{j=0}\bigg((\hat{a}_j-\hat{a}_{j+\frac{n}{2}})\omega^{-j}\bigg)\omega^{-2ij}, equation (26)(26) and (27)(27) become:

a2i=Aimodqa2i+1=Bimodq(27)\begin{aligned} a_{2i}&=A_{i}&\mod q\\ a_{2i+1}&=B_i &\mod q \tag{27} \end{aligned}

With this finding, we just need to calculate AiA_i and BiB_i for 0in210\leq i \leq \frac{n}{2}-1. Notice that AiA_i and BiB_i can be calculated using n2\frac{n}{2} point INTT so if we repeat recursively, we can achieve the best case scenario O(nlogn)O(n\log n) which occurs when nn is a power of 2.

NWC case

Similarly, continuing from equation (17)(17) for INTTψ\mathsf{INTT}^\psi, ignoring n1n^{−1} term, we got:

ai=j=0n1ψ(2ij+i)a^jmodq=ψij=0n1ψ2ija^jmodq=ψi(j=0n21ψ2ija^j+j=0n21ψ2i(j+n2)a^j+n2)modq(28)\begin{aligned} a_i& = \sum_{j=0}^{n-1}\psi^{-(2ij+i)}\hat{a}_j&\mod q \\ & = \psi^{-i}\sum_{j=0}^{n-1}\psi^{-2ij}\hat{a}_j&\mod q \\ &=\psi^{-i}\Bigg(\sum_{j=0}^{\frac{n}{2}-1}\psi^{-2ij}\hat{a}_{j} + \sum_{j=0}^{\frac{n}{2}-1}\psi^{-2i(j+\frac{n}{2})}\hat{a}_{j+\frac{n}{2}}\Bigg)&\mod q\\ \end{aligned}\tag{28}

If we consider the odd and even term, we get:

a2i=ψ2i(j=0n21ψ4ija^j+j=0n21ψ4i(j+n2)a^j+n2)modq=ψ2ij=0n21(a^j+a^j+n2)ψ4ijmodq(29)\begin{aligned} a_{2i}&=\psi^{-2i}\Bigg(\sum^{\frac{n}{2}-1}_{j=0}\psi^{-4ij}\hat{a}_j+\sum^{\frac{n}{2}-1}_{j=0}\psi^{-4i(j+\frac{n}{2})}\hat{a}_{j+\frac{n}{2}}\Bigg) &\mod q \\ &=\psi^{-2i}\sum^{\frac{n}{2}-1}_{j=0}\bigg(\hat{a}_j + \hat{a}_{j+\frac{n}{2}}\Bigg)\psi^{-4ij} &\mod q \\ \end{aligned} \tag{29}
a2i+1=ψ2i1(j=0n21ψ2(2i+1)ja^j+j=0n21ψ2(2i+1)(j+n2)a^j+n2)modq=ψ2i1(j=0n21ψ4ij2ja^j+j=0n21ψ4ij2j2nina^j+n2)modq=ψ2i1j=0n21((a^ja^j+n2)ψ2j)ψ4ijmodq(30)\begin{aligned} a_{2i+1}&=\psi^{-2i-1}\Bigg(\sum^{\frac{n}{2}-1}_{j=0}\psi^{-2(2i+1)j}\hat{a}_j+\sum^{\frac{n}{2}-1}_{j=0}\psi^{-2(2i+1)(j+\frac{n}{2})}\hat{a}_{j+\frac{n}{2}}\Bigg) &\mod q \\ &=\psi^{-2i-1}\Bigg(\sum^{\frac{n}{2}-1}_{j=0}\psi^{-4ij-2j}\hat{a}_j+\sum^{\frac{n}{2}-1}_{j=0}\psi^{-4ij-2j-2ni - n}\hat{a}_{j+\frac{n}{2}}\Bigg) &\mod q \\ &=\psi^{-2i-1}\sum^{\frac{n}{2}-1}_{j=0}\bigg((\hat{a}_j - \hat{a}_{j+\frac{n}{2}})\psi^{-2j}\Bigg)\psi^{-4ij} &\mod q \end{aligned}\tag{30}

Let Ai=j=0n21ψ(4ij+2i)(a^j+a^j+n2)A_{i}=\sum^{\frac{n}{2}-1}_{j=0}\psi^{-(4ij+2i)}(\hat{a}_j + \hat{a}_{j+\frac{n}{2}}) and Bi=j=0n21ψ(4ij+2i)((a^ja^j+n2)ψ2j)B_i=\sum^{\frac{n}{2}-1}_{j=0}\psi^{-(4ij+2i)}\bigg((\hat{a}_j - \hat{a}_{j+\frac{n}{2}})\psi^{-2j}\Bigg) , then equation (29)(29) and (30)(30) becomes:

a2i=Aimodqa2i+1=ψ1Bimodq(31)\begin{aligned} a_{2i}&=A_i &\mod q\\ a_{2i+1}&=\psi^{-1}B_i &\mod q \end{aligned} \tag{31}

With this finding, we just need to calculate AiA_i and BiB_i for 0in210\leq i \leq \frac{n}{2}-1. Notice that AiA_i and BiB_i can be calculated using n2\frac{n}{2} point INTT so if we repeat recursively, we can achieve the best case scenario O(nlogn)O(n\log n) which occurs when nn is a power of 2.

Figure 2. Gentleman-Sande (GS) butterfly graph notation

Figure 2 illustrates how this butterfly operation is denoted as a graph. This figure represents the computation of (A+B)(A+B) and (AB)ψk(A-B)\psi^k .

References:

Written by BATZORIG ZORIGOO of A41

Last updated