Halo2 学习笔记——背景资料之Polynomials（3）

1. 引言

令 A ( X ) A(X) A(X)为基于 F p \mathbb{F}_p Fp​的degree-3多项式： A ( X ) = a 0 + a 1 X + a 2 X 2 + a 3 X 3 A(X)=a_0+a_1X+a_2X^2+a_3X^3 A(X)=a0​+a1​X+a2​X2+a3​X3 其中 a 0 a_0 a0​称为constant term。

degree n − 1 n-1 n−1的多项式，其有 n n n个系数。

通常，将变量 X X X替换为具体的值 x x x，来计算相应的结果 A ( x ) A(x) A(x)——数学上称为“evaluating A ( X ) A(X) A(X) at a point x x x”。（注意，此处的point不要与椭圆曲线上的point混淆。）

多项式的主要属性有：

• d e g ( A ( X ) B ( X ) ) = d e g ( A ( X ) ) + d e g ( B ( X ) ) , d e g ( A ( X ) / B ( X ) ) = d e g ( A ( X ) ) − d e g ( B ( X ) ) deg(A(X)B(X))=deg(A(X))+deg(B(X)), deg(A(X)/B(X))=deg(A(X))-deg(B(X)) deg(A(X)B(X))=deg(A(X))+deg(B(X)),deg(A(X)/B(X))=deg(A(X))−deg(B(X))
• 若 A ( X ) A(X) A(X)的degree为 n − 1 n-1 n−1，则对该多项式的 n n n个不同点进行evaluation，这些evaluation值可完全定义该多项式。换句话说，由这 n n n个不同点的evaluation值，通过多项式插值获得唯一的degree为 n − 1 n-1 n−1的多项式 A ( X ) A(X) A(X)。
• 多项式 A ( X ) A(X) A(X)的系数表示法为： [ a 0 , a 1 , ⋯   , a n − 1 ] [a_0,a_1,\cdots,a_{n-1}] [a0​,a1​,⋯,an−1​]，其点值表示法为： [ ( x 0 , A ( x 0 ) ) , ( x 1 , A ( x 1 ) ) , ⋯   , ( x n − 1 , A ( x n − 1 ) ) ] [(x_0,A(x_0)), (x_1,A(x_1)), \cdots, (x_{n-1},A(x_{n-1}))] [(x0​,A(x0​)),(x1​,A(x1​)),⋯,(xn−1​,A(xn−1​))] 其中 x 0 , x 1 , ⋯   , x n − 1 x_0,x_1,\cdots,x_{n-1} x0​,x1​,⋯,xn−1​为 n n n个不同的值。 这两种方式都可唯一定义同一多项式。

2. Horner’s rule

可借助Horner’s rule来对一个 n − 1 n-1 n−1 degree多项式进行高效evaluation，仅需 n − 1 n-1 n−1个乘法运算 + n − 1 n-1 n−1个加法运算： a 0 + a 1 X + a 2 X 2 + ⋯ + a n − 1 X n − 1 = a 0 + X ( a 1 + X ( a 2 + ⋯ + X ( a n − 2 + X a n − 1 ) ) ) a_0+a_1X+a_2X^2+\cdots+a_{n-1}X^{n-1}=a_0+X(a_1+X(a_2+\cdots+X(a_{n-2}+Xa_{n-1}))) a0​+a1​X+a2​X2+⋯+an−1​Xn−1=a0​+X(a1​+X(a2​+⋯+X(an−2​+Xan−1​)))

3. FFT

FFT可将多项式的系数表示法 和 点值表示法 之间高效相互转换。

点值表示法时，evaluate的point为 n n n-th roots of unity { w 0 , w 1 , ⋯   , w n − 1 } \{w^0,w^1,\cdots,w^{n-1}\} {w0,w1,⋯,wn−1}，其中 w w w为a primitive n n n-th root of unity。

根据roots of unity的对城乡，FFT每轮运算将reduce the evaluation into a problem only half the size。因此，通常使用的多项式长度为some power of two，即 n = 2 k n=2^k n=2k，从而可apply the halving reduction recursively。

3.1 将FFT用于快速多项式乘法

如需计算 A ( X ) ⋅ B ( X ) = C ( X ) A(X)\cdot B(X)=C(X) A(X)⋅B(X)=C(X)，若采用系数表示法时，需要进行 O ( n 2 ) O(n^2) O(n2)次运算： A ( X ) = a 0 + a 1 X + a 2 X 2 + ⋯ + a n − 1 X n − 1 A(X)=a_0+a_1X+a_2X^2+\cdots+a_{n-1}X^{n-1} A(X)=a0​+a1​X+a2​X2+⋯+an−1​Xn−1 B ( X ) = b 0 + b 1 X + b 2 X 2 + ⋯ + b n − 1 X n − 1 B(X)=b_0+b_1X+b_2X^2+\cdots+b_{n-1}X^{n-1} B(X)=b0​+b1​X+b2​X2+⋯+bn−1​Xn−1 C ( X ) = A ( X ) ⋅ B ( X ) = a 0 ⋅ ( b 0 + b 1 X + b 2 X 2 + ⋯ + b n − 1 X n − 1 ) + a 1 X ⋅ ( b 0 + b 1 X + b 2 X 2 + ⋯ + b n − 1 X n − 1 ) + ⋯ + a n − 1 X n − 1 ⋅ ( b 0 + b 1 X + b 2 X 2 + ⋯ + b n − 1 X n − 1 ) C(X)=A(X)\cdot B(X)=a_0\cdot (b_0+b_1X+b_2X^2+\cdots+b_{n-1}X^{n-1})\\+ a_1X\cdot (b_0+b_1X+b_2X^2+\cdots+b_{n-1}X^{n-1})\\ +\cdots \\+ a_{n-1}X^{n-1}\cdot (b_0+b_1X+b_2X^2+\cdots+b_{n-1}X^{n-1}) C(X)=A(X)⋅B(X)=a0​⋅(b0​+b1​X+b2​X2+⋯+bn−1​Xn−1)+a1​X⋅(b0​+b1​X+b2​X2+⋯+bn−1​Xn−1)+⋯+an−1​Xn−1⋅(b0​+b1​X+b2​X2+⋯+bn−1​Xn−1)

若采用点值表示法，则多项式乘法仅需 O ( n ) O(n) O(n)次运算： A ： { ( x 0 , A ( x 0 ) ) , ( x 1 , A ( x 1 ) ) , ⋯   , ( x n − 1 , A ( x n − 1 ) ) } A：\{(x_0,A(x_0)), (x_1,A(x_1)),\cdots,(x_{n-1}, A(x_{n-1}))\} A：{(x0​,A(x0​)),(x1​,A(x1​)),⋯,(xn−1​,A(xn−1​))} B ： { ( x 0 , B ( x 0 ) ) , ( x 1 , B ( x 1 ) ) , ⋯   , ( x n − 1 , B ( x n − 1 ) ) } B：\{(x_0,B(x_0)), (x_1,B(x_1)),\cdots,(x_{n-1}, B(x_{n-1}))\} B：{(x0​,B(x0​)),(x1​,B(x1​)),⋯,(xn−1​,B(xn−1​))} C ： { ( x 0 , A ( x 0 ) B ( x 0 ) ) , ( x 1 , A ( x 1 ) B ( x 1 ) ) , ⋯   , ( x n − 1 , A ( x n − 1 ) B ( x n − 1 ) ) } C：\{(x_0,A(x_0)B(x_0)), (x_1,A(x_1)B(x_1)),\cdots,(x_{n-1}, A(x_{n-1})B(x_{n-1}))\} C：{(x0​,A(x0​)B(x0​)),(x1​,A(x1​)B(x1​)),⋯,(xn−1​,A(xn−1​)B(xn−1​))} 其中 C C C中的值是直接multiplied pointwise的。

进行快速多项式乘法运算的主要步骤为：

• 1）Evaluate polynomials at all n n n points。
• 2）Perform fast pointwise multiplication in the evaluation representation O ( n ) O(n) O(n)。
• 3）将结果再转换为系数表示法（通过IFFT）。

主要难点在于高效的对多项式进行evaluate和插值。 直观地，evaluate a polynomial at n n n points需要 O ( n 2 ) O(n^2) O(n2)次运算（每个point采用Horner’s rule需 O ( n ) O(n) O(n)次运算， n n n个point对应为 O ( n 2 ) O(n^2) O(n2)次运算）： [ A ( 1 ) A ( w ) A ( w 2 ) ⋮ A ( w n − 1 ) ] = [ 1 1 1 ⋯ 1 1 w w 2 ⋯ w n − 1 1 w 2 w 2 ⋅ 2 ⋯ w 2 ⋅ ( n − 1 ) ⋮ ⋮ ⋮ ⋮ 1 w n − 1 w 2 ( n − 1 ) ⋯ w ( n − 1 ) 2 ] ⋅ [ a 0 a 1 a 2 ⋮ a n − 1 ] \begin{bmatrix} A(1) \\ A(w) \\ A(w^2) \\ \vdots \\ A(w^{n-1}) \end{bmatrix} = \begin{bmatrix} 1& 1 & 1 & \cdots & 1\\ 1& w & w^2 & \cdots & w^{n-1} \\ 1& w^2 & w^{2\cdot 2} & \cdots & w^{2\cdot (n-1)} \\ \vdots & \vdots & \vdots & &\vdots \\ 1 & w^{n-1} & w^{2(n-1)} & \cdots & w^{(n-1)^2} \end{bmatrix} \cdot \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1} \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎡​A(1)A(w)A(w2)⋮A(wn−1)​⎦⎥⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎢⎡​111⋮1​1ww2⋮wn−1​1w2w2⋅2⋮w2(n−1)​⋯⋯⋯⋯​1wn−1w2⋅(n−1)⋮w(n−1)2​⎦⎥⎥⎥⎥⎥⎤​⋅⎣⎢⎢⎢⎢⎢⎡​a0​a1​a2​⋮an−1​​⎦⎥⎥⎥⎥⎥⎤​

可将以上多项式表示为： A ^ = V w ⋅ A \hat{\mathbf{A}}=\mathbf{V}_w\cdot \mathbf{A} A^=Vw​⋅A 其中 A ^ \hat{\mathbf{A}} A^可称为 A \mathbf{A} A的离散傅里叶变换（DFT）， V w \mathbf{V}_w Vw​称为Vandermonde matrix。

3.2 The (radix-2) Cooley-Tukey algorithm

将size为 n n n的DFT分为2个交错的size为 n / 2 n/2 n/2的DFT。 对于多项式 A ( X ) = a 0 + a 1 X + a 2 X 2 + ⋯ + a n − 1 X n − 1 A(X)=a_0+a_1X+a_2X^2+\cdots+a_{n-1}X^{n-1} A(X)=a0​+a1​X+a2​X2+⋯+an−1​Xn−1，可将其分为奇数项和偶数项： A e v e n = a 0 + a 2 X + ⋯ + a n − 2 X n / 2 − 1 A_{even}=a_0+a_2X+\cdots+a_{n-2}X^{n/2-1} Aeven​=a0​+a2​X+⋯+an−2​Xn/2−1 A o d d = a 1 + a 3 X + ⋯ + a n − 1 X n / 2 − 1 A_{odd}=a_1+a_3X+\cdots +a_{n-1}X^{n/2-1} Aodd​=a1​+a3​X+⋯+an−1​Xn/2−1 然后基于此，有 A ( X ) = A e v e n ( X 2 ) + X A o d d ( X 2 ) A(X)=A_{even}(X^2)+XA_{odd}(X^2) A(X)=Aeven​(X2)+XAodd​(X2)

对 A ( X ) A(X) A(X) evaluate at points w n i , w n n 2 + i w_n^i, w_n^{\frac{n}{2}+i} wni​,wn2n​+i​，其中 i ∈ [ 0 , ⋯   , n 2 − 1 ] i\in[0,\cdots,\frac{n}{2}-1] i∈[0,⋯,2n​−1]，有： A ( w n i ) = A e v e n ( ( w n i ) 2 ) + w n i A o d d ( ( w n i ) 2 ) A(w_n^i)=A_{even}((w_n^i)^2)+w_n^iA_{odd}((w_n^i)^2) A(wni​)=Aeven​((wni​)2)+wni​Aodd​((wni​)2) A ( w n n 2 + i ) = A e v e n ( ( w n n 2 + i ) 2 ) + w n n 2 + i A o d d ( ( w n n 2 + i ) 2 ) = A e v e n ( ( − w n i ) 2 ) − w n i A o d d ( ( − w n i ) 2 ) 【 ← ( 根 据 n e g a t i o n l e m m a ) 】 = A e v e n ( ( w n i ) 2 ) − w n i A o d d ( ( w n i ) 2 ) A(w_n^{\frac{n}{2}+i})=A_{even}((w_n^{\frac{n}{2}+i})^2)+w_n^{\frac{n}{2}+i}A_{odd}((w_n^{\frac{n}{2}+i})^2)\\ =A_{even}((-w_n^i)^2)-w_n^iA_{odd}((-w_n^i)^2) 【\leftarrow (根据negation lemma)】\\ =A_{even}((w_n^i)^2)-w_n^iA_{odd}((w_n^i)^2) A(wn2n​+i​)=Aeven​((wn2n​+i​)2)+wn2n​+i​Aodd​((wn2n​+i​)2)=Aeven​((−wni​)2)−wni​Aodd​((−wni​)2)【←(根据negationlemma)】=Aeven​((wni​)2)−wni​Aodd​((wni​)2)

由上可看出，两者存在一定的对称性。仅需evaluate A e v e n A_{even} Aeven​和 A o d d A_{odd} Aodd​ over half the domain ( w n 0 ) 2 , ( w n ) 2 , ⋯   , ( w n n 2 − 1 ) 2 (w_n^0)^2,(w_n)^2,\cdots,(w_n^{\frac{n}{2}-1})^2 (wn0​)2,(wn​)2,⋯,(wn2n​−1​)2，其中 i = [ 0 , ⋯   , n 2 − 1 ] i=[0,\cdots, \frac{n}{2}-1] i=[0,⋯,2n​−1]（根据halving lemma）。 即意味着，可将length- n n n DFT 转换为 2个length- n 2 \frac{n}{2} 2n​ DFTs。

当 n = 2 k n=2^k n=2k时（为power of two，若不够可zero-padding），然后递归使用divide-and-conquer策略。根据Master Theorem，相应的evaluation算法仅需 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2​n)次运算，也称为Fast Fourier Transform (FFT)。

3.3 Inverse FFT

至此，已完成polynomial evaluation 和 multiply pointwise，现在需要将 C ( X ) = A ( X ) ⋅ B ( X ) C(X)=A(X)\cdot B(X) C(X)=A(X)⋅B(X)由 点值表示法 转换为 系数表示法。仅需，在点值表示法 上进行FFT运算：

• 1）将Vandermonde matrix中的 w i w^i wi替换为 w − i w^{-i} w−i
• 2）将最终结果乘以 1 / n 1/n 1/n

即： A = 1 n V w − 1 ⋅ A ^ \mathbf{A}=\frac{1}{n}\mathbf{V}_{w^{-1}}\cdot \hat{\mathbf{A}} A=n1​Vw−1​⋅A^

IFFT与FFT具有类似的格式，详细参见 The Fast Fourier Transform and Polynomial Multiplication。

4. The Schwartz-Zippel lemma

The Schwartz-Zippel lemma表达的是“different polynomials are different at most points”： 令 p ( x 1 , x 2 , ⋯   , x n ) p(x_1,x_2,\cdots,x_n) p(x1​,x2​,⋯,xn​)为nonzero polynomial of n n n variables with degree d d d，令 S S S为a finite set of numbers with at least d d d elements in it。若从 S S S中随机选出 α 1 , α 2 , ⋯   , α n \alpha_1,\alpha_2,\cdots,\alpha_n α1​,α2​,⋯,αn​，则有： Pr [ p ( α 1 , α 2 , ⋯   , α n ) = 0 ] ≤ d ∣ S ∣ \text{Pr}[p(\alpha_1,\alpha_2,\cdots,\alpha_n)=0]\leq \frac{d}{|S|} Pr[p(α1​,α2​,⋯,αn​)=0]≤∣S∣d​

对于degree为 d d d的单变量非零多项式 p ( X ) p(X) p(X)，即意味着最多有 d d d个根。

The Schwartz-Zippel lemma用于polynomial equality testing： 已知2个多变量多项式， p 1 ( x 1 , ⋯   , x n ) p_1(x_1,\cdots, x_n) p1​(x1​,⋯,xn​)的degree为 d 1 d_1 d1​， p 2 ( x 1 , ⋯   , x n ) p_2(x_1,\cdots,x_n) p2​(x1​,⋯,xn​)的degree为 d 2 d_2 d2​，可随机选择 α 1 , ⋯   , α n ← S \alpha_1,\cdots,\alpha_n\leftarrow S α1​,⋯,αn​←S，其中 ∣ S ∣ ≥ ( d 1 + d 2 ) |S|\geq (d_1+d_2) ∣S∣≥(d1​+d2​)，测试 p 1 ( α 1 , ⋯   , α n ) − p 2 ( α 1 , ⋯   , α n ) = 0 p_1(\alpha_1,\cdots,\alpha_n)-p_2(\alpha_1,\cdots,\alpha_n)=0 p1​(α1​,⋯,αn​)−p2​(α1​,⋯,αn​)=0是否成立。若 p 1 , p 2 p_1,p_2 p1​,p2​这两个多项式完全相同，必然成立。若两者不同，则该等式成立的概率不高于 m a x ( d 1 , d 2 ) ∣ S ∣ \frac{max(d_1,d_2)}{|S|} ∣S∣max(d1​,d2​)​。

5. Vanishing polynomial

对于order n n n multiplicative subgroup H \mathcal{H} H with primitive root of unity w w w，对于所有的 w i ∈ H , i ∈ [ n − 1 ] w^i\in\mathcal{H},i\in[n-1] wi∈H,i∈[n−1]，有 ( w i ) n = ( w n ) i = ( w 0 ) i = 1 (w^i)^n=(w^n)^i=(w^0)^i=1 (wi)n=(wn)i=(w0)i=1，换句话说： Z H ( X ) = X n − 1 = ( X − w 0 ) ( X − w 1 ) ( X − w 2 ⋯ ( X − w n − 1 ) Z_H(X)=X^n-1=(X-w^0)(X-w^1)(X-w^2\cdots(X-w^{n-1}) ZH​(X)=Xn−1=(X−w0)(X−w1)(X−w2⋯(X−wn−1) H \mathcal{H} H中的每个元素为 Z H ( X ) Z_H(X) ZH​(X)的根。称 Z H ( X ) Z_H(X) ZH​(X)为the vanishing polynomial over H \mathcal{H} H，因为其evaluate to zero on all elements of H \mathcal{H} H。

vanishing polynomial 用于验证polynomial constraints时将特别实用。如，为了验证 A ( X ) + B ( X ) = C ( X ) A(X)+B(X)=C(X) A(X)+B(X)=C(X) over H \mathcal{H} H，可改为验证 A ( X ) + B ( X ) − C ( X ) A(X)+B(X)-C(X) A(X)+B(X)−C(X)为 some multiple of Z H ( X ) Z_H(X) ZH​(X)。换句话说，若将constraints除以vanishing polynomial，仍然可产生某多项式 A ( X ) + B ( X ) − C ( X ) Z H ( X ) = H ( X ) \frac{A(X)+B(X)-C(X)}{Z_H(X)}=H(X) ZH​(X)A(X)+B(X)−C(X)​=H(X)，则可说明 A ( X ) + B ( X ) − C ( X ) = 0 A(X)+B(X)-C(X)=0 A(X)+B(X)−C(X)=0 over H \mathcal{H} H。

6. Lagrange basis functions

多项式通常以monomial basis（如 X , X 2 , ⋯   , X n X,X^2,\cdots,X^n X,X2,⋯,Xn）来表示，但是，当机遇multiplicative subgroup of order n n n时，采用Lagrange basis表示更自然。

对于order- n n n multiplicative subgroup H \mathcal{H} H with primitive root of unity w w w，该subgroup的Lagrange basis为a set of functions { L i } i = 0 n − 1 \{\mathcal{L}_i\}_{i=0}^{n-1} {Li​}i=0n−1​，其中： L i ( w j ) = { 1 if  i = j , 0 otherwise. \mathcal{L}_i(w^j)=\left\{\begin{matrix} 1 & \text{if } i=j,\\ 0 & \text{otherwise.} \end{matrix}\right. Li​(wj)={10​if i=j,otherwise.​

可将 L i ( w j ) \mathcal{L}_i(w^j) Li​(wj)更精简的表示为 δ i j \delta_{ij} δij​，其中 δ \delta δ为the Kronecker delta function。

至此，可将多项式表示为a linear combination of Lagrange basis functions： A ( X ) = ∑ i = 0 n − 1 a i L i ( X ) , X ∈ H A(X)=\sum_{i=0}^{n-1}a_i\mathcal{L}_i(X), X\in\mathcal{H} A(X)=∑i=0n−1​ai​Li​(X),X∈H 即等价为说， p ( X ) p(X) p(X) evaluates to a 0 a_0 a0​ at w 0 w^0 w0, to a 1 a_1 a1​ at w 1 w^1 w1, to a 2 a_2 a2​ at w 2 w^2 w2等等。

当基于multiplicative subgroup时，Lagrange basis function具有很方便的sparse表示形式： L i ( X ) = c i ⋅ ( X n − 1 ) X − w i \mathcal{L}_i(X)=\frac{c_i\cdot (X^n-1)}{X-w^i} Li​(X)=X−wici​⋅(Xn−1)​ 其中 c i c_i ci​为barycentric weight。详细可参看Barycentric Lagrange Interpolation*。 当 i = 0 i=0 i=0时，有 c = 1 / n ⇒ L 0 ( X ) = 1 n ( X n − 1 ) X − 1 c=1/n\Rightarrow \mathcal{L}_0(X)=\frac{1}{n}\frac{(X^n-1)}{X-1} c=1/n⇒L0​(X)=n1​X−1(Xn−1)​。

对于evaluation point set { x 0 , x 1 , ⋯   , x n − 1 } \{x_0,x_1,\cdots,x_{n-1}\} {x0​,x1​,⋯,xn−1​}，若不假设 x i x_i xi​为multiplicative subgroup，仍可采用Lagrange 多项式 L i \mathcal{L}_i Li​来表示： L i ( X ) = ∏ j ≠ i X − x j x i − x j , i ∈ [ 0.. n − 1 ] \mathcal{L}_i(X)=\prod_{j\neq i}\frac{X-x_j}{x_i-x_j}, i\in[0..n-1] Li​(X)=∏j​=i​xi​−xj​X−xj​​,i∈[0..n−1]

对于每个 X = x j ≠ x i X=x_j\neq x_i X=xj​​=xi​，都有零分子项 ( x j − x j ) (x_j-x_j) (xj​−xj​)，从而使整个值为0。若 X = x i X=x_i X=xi​，有 x i − x j x i − x j \frac{x_i-x_j}{x_i-x_j} xi​−xj​xi​−xj​​，结果为1。从而可实现desired Kronecker delta behaviour L i ( x j ) = δ i j \mathcal{L}_i(x_j)=\delta_{ij} Li​(xj​)=δij​ on the set { x 0 , x 1 , ⋯   , x n − 1 } \{x_0,x_1,\cdots,x_{n-1}\} {x0​,x1​,⋯,xn−1​}。

6.1 Lagrange interpolation

已知多项式的点值表示： A : { ( x 0 , A ( x 0 ) ) , ( x 1 , A ( x 1 ) ) , ⋯   , ( x n − 1 , A ( x n − 1 ) ) } A: \{(x_0,A(x_0)), (x_1,A(x_1)), \cdots, (x_{n-1},A(x_{n-1}))\} A:{(x0​,A(x0​)),(x1​,A(x1​)),⋯,(xn−1​,A(xn−1​))}

可基于Lagrange basis来构建其 系数表示： A ( X ) = ∑ i = 0 n − 1 A ( x i ) L i ( X ) A(X)=\sum_{i=0}^{n-1}A(x_i)\mathcal{L}_i(X) A(X)=∑i=0n−1​A(xi​)Li​(X) 其中 X ∈ { x 0 , x 1 , ⋯   , x n − 1 } X\in\{x_0,x_1,\cdots,x_{n-1}\} X∈{x0​,x1​,⋯,xn−1​}。

参考资料

[1] Halo2 背景资料之Polynomials