這個週末有空，講講我對FFT的理解。方便學習零知識證明的小夥伴理解這部分內容。從頭講起，零知識證明Groth26演算法基於QAP問題：
利用Groth26計算證明之前，需要計算出H。目前，普遍採用的是FFT演算法。
1. FFT計算原理
學習FFT計算原理，還是要看演算法導論（Introduction-to-Algorithms）的第30章（Polynomials and the FFT)。演算法導論，講東西，來龍去脈講的比較清楚，邏輯性比較強，也比較細緻。該章節從多項式的表示開始，多項式可以用兩種表示方法：係數表示和點值表示。
係數表示，對多項式加法友好，時間複雜度是O(n)，但是多項式乘法不友好，採用多項式一項項的相乘，時間複雜度為 O(n**2)。點值表示，對多項式乘法友好，時間複雜度是 O(n)，但是多項式加法不友好。
DFT，採用特殊的點，計算值。這些特殊的點，就是單位根的冪次。採用這些特殊點的情況下，係數表示和點值表示之間可以透過FFT（快速傅立葉變換）計算完成。時間複雜度是O(nlogn)。
演算法導論上這個圖，可以很好的解釋這些計算之間的關係：
如果是係數表示，多項式乘法的計算複雜度為O(n**2)。如果先轉化為點值表示，點值表示相乘，再轉化回係數表示，計算複雜度為O(nlogn)。
n次單位根
存在n個n次的單位根。這些單位根滿足w**n = 1。
這些單位根，存在一些性質或者定理：
FFT的基本原理
DFTn(a)的計算採用FFT的計算，時間複雜度為O (nlogn)。原理是，將多項式分解成奇偶兩部分（假設n為2的冪次，n不為2的冪次也有相應的演算法，後話）：
也就是說，計算A(x)的對應的值，可以分解成兩個子多項式（奇偶），每個多項式的點是之前的平方。遞迴的角度可以看出，這些子多項式，可以進一步劃分分更小的多項式。整個計算的複雜度：
如果把輸入點也分成兩部分，每部分是n/2個，k的範圍是0~n/2，則:
這個就是傳說中的“蝶形計算”。當兩個子多項式的值計算完成後，原來多項式的兩個相差n/2的點的值，是兩個子多項式的值的一加一減。
整個計算演算法的虛擬碼如下：
其中的作用在第二個子多項式結果上的w_n^k，稱為旋轉因子。整個蝶形運算可以用視覺化的圖形表示如下：
8階多項式示例
演算法導論清晰的給出了8階多項式的FFT的計算過程：
在stage s=1的情況下，也就是最“底層”的兩個1階多項式合併。旋轉因子是w_2^0。注意這一層的輸出結果，會作為下一層stage s=2的輸入，這一層的旋轉因子是w_4^{0,1}。這一層要處理的是“兩個”2階多項式的合併。在奇偶劃分的情況下，第一個/第二個元素和第三個/四個元素（跨度為2）做蝶形運算。依次類推，直到stage s=3 做完。
整個過程，可以透過Merkle樹形象表示：
注意最底層的元素的位置，經過遞迴的劃分已經不是順序的。演算法導論也總結了相應的計算方法，感興趣的小夥伴，可以自行檢視。
可以返回頭，體會體會這個公式：
因為特殊的取點的原因（w^2相當於階降低了一半），子多項式的值也是結果多項式的一半。因為在取點分一半（恰好是子多項式的階），又因為旋轉因子正好是正負，所以存在蝶形關係。每一層的子多項式的元素翻倍。
2. FFT一般性計算擴充套件
在理解了2分的FFT的計算邏輯後，可以擴充套件到一般性計算。推薦另外一個網站（注意多項式符號和上文有點區別）：
http://www.bealto.com/gpu-fft2_fft.html
多項式不再拆解成“奇偶”兩部分，而是分成P份，每份為Q個元素：
其中，x_u為係數。u的範圍是0-P-1，先定義一下，在這種劃分下的DFT計算：
DFT_Q代表了有Q個元素，x[u]代表了Q個元素序列，每個元素序列跨度為P，P*Q=n。
如果把輸入也切割成P份（就像二分情況下，將輸入分成兩份一樣），k可以表達成k=v+Qj，v=0..Q-1，j=0..P-1。其中，DFT_Q (x[u])記為z[u]。
也就是說，P*Q分組的情況下，蝶形運算如下圖：
進一步，可以將y的每個元素的計算看成一個新的DFT_P：
在理解這些的前提下，看看網站給出的按照P*Q分組計算的示意圖就比較清晰：
整個FFT的計算由三部分組成：
1/ P個DFT_Q計算（z[0], z[1], ...z[P-1]) 2/ 乘上Twiddle 3/ Q個DFT_P計算
在Q個DFT_P計算之後，需要將P個計算資料“分散”到以Q為偏移的具體的位置。
總結：
零知識證明Groth26的計算中為了計算H，採用了FFT計算。FFT的蝶形運算是理解FFT計算的基礎。二分情況下的計算，相對清晰，演算法導論給出了詳細的推導過程。P*Q的一般性計算推導，相對複雜一些。
