多線性擴展多項式：計算擴展多項式的係數
讓 $ \textbf{a}=\left[10, 32, 57, 81\right] $ 和 $ x={0, 1, 2, 3} $ .
然後向量的多線性擴展 $ \textbf{a} $ 是多項式， $ f_\textbf{a}(x_2, x_1) = 10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1 $ ， 在哪裡 $ x_2 $ 和 $ x_1 $ 是第二位和第一位 $ x $ 分別。
因此， $$ x = 0, f_\textbf{a}(0, 0) = \textbf{a}[0] = 10 $$ $$ x = 1, f_\textbf{a}(0, 1) = \textbf{a}[1] = 32 $$ $$ x = 2, f_\textbf{a}(1, 0) = \textbf{a}[2] = 57 $$ $$ x = 3, f_\textbf{a}(1, 1) = \textbf{a}[3] = 81 $$
展開多項式： $$ \begin{align} f_\textbf{a}(x_2, x_1) &= 10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1 \ &= 2 x_2 x_1 + 22 x_1 + 47 x_2 + 10 \end{align} $$
是否有一種算法可以直接計算擴展多項式的係數 $ f_\textbf{a} = 2 x_2 x_1 + 22 x_1 + 47 x_2 + 10 $ 沒有天真地擴展多項式 $ 10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1 $ ?
這可以在 $ O(n2^n) $ ， 在哪裡 $ n $ 是變數的數量（天真的擴展需要 $ O(2^{2n}) $ 在最壞的情況下）。
這是一種稱為“對子集/超集/子遮罩/超級遮罩求和”的標準技術。一個常見的例子是 ANF 計算，它在 $ GF(2) $ 所以它使用 XOR 操作。這里基本相同，但由於我們使用整數，所以我們現在必須關心符號。
這個想法是遞歸地應用矩陣 $$ M=\begin{pmatrix} 1 & 0\ -1 & 1\ \end{pmatrix} $$ 這對應於應用矩陣 $ M^{\otimes n} $ 到輸入。
為了進一步說明這個想法，看看當我們對一位（變數）應用轉換時會發生什麼，比如說 $ x_1 $ . 我們有 $$ f_a = 10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1. $$ 什麼 $ M $ 告訴我們要做的是考慮包含以下項的係數 $ (1-x_1) $ , 並從相同的項的係數中減去那些，除了 $ (1-x_1) $ 被替換為 $ x_1 $ . 對於上面的例子，它告訴從 32 中減去 10，從 81 中減去 57。很容易看出這個動作對應於擴展術語 $ (1-x_1) $ . 通過對所有變數重複此過程，我們可以獲得所需的結果。
這是python程式碼。
def ext(a): if len(a) == 1: return (a[0],) n = len(a) h = n // 2 l = ext(a[:h]) r = ext(a[h:]) return l + tuple(vr - vl for vl, vr in zip(l, r)) a = [10, 32, 57, 81] b = ext(a) print(b) # (10, 22, 47, 2)澄清符號。
- 在輸入數組中 $ a $ , $ a_i $ 是乘積的係數： $ x_j $ 如果 $ j $ - 第一點 $ i $ 在二進製表示中是 1 或 $ 1-x_j $ 否則;
- 在輸出數組中 $ b $ , $ b_i $ 是乘積的係數 $ x_j $ 如果 $ j $ - 第一點 $ i $ 在二進製表示中是 1 或 $ 1 $ 否則。
位從最高有效位開始計數。例如對於 $ n=3 $ , $ i=3 $ 在輸入對應於 $ (1-x_1)x_2x_3 $ ， 和 $ i=3 $ 在輸出中對應於 $ x_2x_3 $ .