GF(2) 中多項式方程的函式
讓
F(a,b,c,d,e)是一個返回 的ith位的函式0x3A5C742E，其中i=a*2^4+b*2^3+c*2^2+d*2+e和 i 是從最低有效位的偏移量。作者第 33/200 頁，第 2.3.4 章指出，為了找到等效輸出的多項式，您可以使用 k-maps。後來他說計算後的方程是：
NLF(a,b,c,d,e) = d+e+ac+ae+bc+be+cd+de+ade+ace+abd+abc這是我的 k-map 計算：
00 01 11 10 000 0 1 1 1 001 0 1 0 0 011 1 1 0 1 010 0 0 0 1 110 0 1 1 0 111 1 1 0 0 101 1 0 0 1 100 0 0 1 1行在哪裡
abc，列在哪裡de現在從這個圖中我看不出如何生成給定的方程。僅消除 1 個變數。所以所有生成的方程應該至少是 4 度。
那麼問題來了，他的方程是怎麼產生的呢？
公式
$$ d+e+ac+ae+bc+be+cd+de+ade+ace+abd+abc $$ 是代數範式（ANF）。這是我們的布爾函式關於 $ \mathbb F_2 $ -基礎 $ {a^ib^jc^kd^le^m\mid i,j,k,l,m\in{0,1}} $ 布爾函式空間的 $ \mathbb F_2^5\to\mathbb F_2 $ . 特別要注意“ $ + $ " 是異或。 我不認為卡諾圖在這種情況下很有幫助，因為將 $ 1 $ 表中的條目變得有點棘手，因為你必須避免否定。最後，它起作用了，但它不僅僅是繪製幾個矩形並閱讀正確的術語。
相反，上面的代數描述提供了一種簡單的迭代方法來計算 ANF。（另請參閱此 Math.SE 文章。）基本上，我們函式的 ANF $ f $ 看起來像這樣：
$$ f(a,b,c,d,e) = x_0+ x_aa+x_bb+x_cc+x_dd+x_ee+ x_{ab}ab+x_{ac}ac+x_{ad}ad+x_{ae}ae+x_{bc}bc+x_{bd}bd+x_{be}be+x_{cd}cd+x_{ce}ce+x_{de}de+ x_{abc}abc+x_{abd}abd+x_{abe}abe+x_{acd}acd+x_{ace}ace+x_{ade}ade+x_{bcd}bcd+x_{bce}bce+x_{bde}bde+x_{cde}cde+ x_{abcd}abcd+x_{abce}abce+x_{abde}abde+x_{acde}acde+x_{bcde}bcde+ x_{abcde}abcde \text, $$ 我們對計算唯一係數感興趣 $ x_\ast\in{0,1} $ . 為此，我們限制目標函式 $ f $ ：將足夠多的變數設置為零將充分簡化上述公式以完全確定另一個係數。
- 首先，我們考慮“限制” $ f(0,0,0,0,0) $ . 通過上面的公式，這只是 $ x_0 $ .
- 接下來，我們考慮 $ f(a,0,0,0,0)=x_0+x_aa $ ： 自從 $ x_0 $ 已經知道， $ x_a $ 可以恢復為 $ f(1,0,0,0,0)+x_0 $ （模組 $ 2 $ 當然）。係數 $ x_b $ 通過 $ x_e $ 類似地計算。
- 為了 $ x_{ab} $ ， 考慮 $ f(a,b,0,0,0)=x_0+x_aa+x_bb+x_{ab}ab $ : 係數 $ x_0 $ , $ x_a $ 和 $ x_b $ 是已知的，所以我們可以計算 $ x_{ab}=f(1,1,0,0,0)+x_0+x_a+x_b $ . 再次， $ x_{ac} $ 通過 $ x_{de} $ 工作完全相同。
- 重複這個過程最終會產生所有的係數。
如果您只想要結果而不需要手動完成該過程，請注意sage提供了相關功能。