也就是说，P*Q分组的环境下，蝶形运算如下图：
在stage s=1的环境下，也就是最“底层”的两个1阶多项式归并。旋转因子是w_2^0。留意这一层的输出功效，会作为下一层stage s=2的输入，这一层的旋转因子是w_4^{0,1}。这一层要处理惩罚的是“两个”2阶多项式的归并。在奇偶分另外环境下，第一个/第二个元素和第三个/四个元素（跨度为2）做蝶形运算。依次类推，直到stage s=3 做完。
算法导论上这个图，可以很好的表明这些计较之间的干系：
个中，x_u为系数。u的范畴是0-P-1，先界说一下，在这种分别下的DFT计较：
总结：这个就是传说中的“蝶形计较”。当两个子多项式的值计较完成后，本来多项式的两个相差n/2的点的值，是两个子多项式的值的一加一减。
http://www.bealto.com/gpu-fft2_fft.html
在领略这些的前提下，看看网站给出的凭据P*Q分组计较的示意图就较量清晰：
FFT的根基道理
假如把输入点也分成两部门，每部门是n/2个，k的范畴是0~n/2，则:
在Q个DFT_P计较之后，，需要将P个计较数据“分手”到以Q为偏移的详细的位置。
可以返转头，体会体会这个公式：
这个周末有空，讲讲我对FFT的领略。利便进修零常识证明的小同伴领略这部门内容。从新讲起，零常识证明Groth16算法基于QAP问题：
整个计较算法的伪代码如下：
假如是系数暗示，多项式乘法的计较巨大度为O(n**2)。假如先转化为点值暗示，点值暗示相乘，再转化回系数暗示，计较巨大度为O(nlogn)。
个中的浸染在第二个子多项式功效上的w_n^k，称为旋转因子。整个蝶形运算可以用可视化的图形暗示如下：
2. FFT一般性计较扩展
这些单元根，存在一些性质可能定理：
因为非凡的取点的原因（w^2相当于阶低落了一半），子多项式的值也是功效多项式的一半。因为在取点分一半（刚好是子多项式的阶），又因为旋转因子正好是正负，所以存在蝶形干系。每一层的子多项式的元素翻倍。
在领略了2分的FFT的计较逻辑后，可以扩展到一般性计较。推荐别的一个网站（留意多项式标记和上文有点区别）：
进一步，可以将y的每个元素的计较当作一个新的DFT_P：
算法导论清晰的给出了8阶多项式的FFT的计较进程：
零常识证明Groth16的计较中为了计较H，回收了FFT计较。FFT的蝶形运算是领略FFT计较的基本。二分环境下的计较，相对清晰，算法导论给出了具体的推导进程。P*Q的一般性计较推导，相对巨大一些。DFTn(a)的计较回收FFT的计较，时间巨大度为O (nlogn)。道理是，将多项式解析成奇偶两部门（假设n为2的幂次，n不为2的幂次也有相应的算法，后话）：
多项式不再拆解成“奇偶”两部门，而是分成P份，每份为Q个元素：
操作Groth16计较证明之前，需要计较出H。今朝，普遍回收的是FFT算法。
DFT_Q代表了有Q个元素，x[u]代表了Q个元素序列，每个元素序列跨度为P，P*Q=n。
8阶多项式示例
DFT，回收非凡的点，计较值。这些非凡的点，就是单元根的幂次。回收这些非凡点的环境下，系数暗示和点值暗示之间可以通过FFT（快速傅立叶调动）计较完成。时间巨大度是O(nlogn)。
进修FFT计较道理，照旧要看算法导论（Introduction-to-Algorithms）的第30章（Polynomials and the FFT)。算法导论，讲对象，来龙去脉讲的较量清楚，逻辑性较量强，也较量细致。该章节从多项式的暗示开始，多项式可以用两种暗示要领：系数暗示和点值暗示。
整个进程，可以通过Merkle树形象暗示：n次单元根
系数暗示，对多项式加法友好，时间巨大度是O(n)，可是多项式乘法不友好，回收多项式一项项的相乘，时间巨大度为 O(n**2)。点值暗示，对多项式乘法友好，时间巨大度是 O(n)，可是多项式加法不友好。
假如把输入也切割成P份（就像二分环境下，将输入分成两份一样），k可以表告竣k=v+Qj，v=0..Q-1，j=0..P-1。个中，DFT_Q (x[u])记为z[u]。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
