降低 XOR 的實施成本
假設我們要在二進制有限域中實現以下方程。
$$ \begin{array}{l}\tag{1} y_{{1}}=x_{{1}}\oplus x_{{2}}\oplus x_{{7}}\oplus x_{{8}},\ y_{{2}}=x_{{1}}\oplus x_{{2}}\oplus x_{{6}}\oplus x_{{8}},\ y_{{3}}=x_{{1}}\oplus x_{{2}}\oplus x_{{7}},\ y_{{4}}=x_{{2}}\oplus x_{{8}}. \end{array} $$
*我的問題：*是否可以在 $ (1) $ 有五個 $ \operatorname{XOR} $ ?
我的嘗試結果是六個 $ \operatorname{XOR} $ 為實施成本。例如;
$$ \begin{array}{l}\tag{2} u_1=x_1\oplus x_2,\ u_2=x_2\oplus x_8=y_4\ u_3=x_6\oplus x_8,\ u_4=u_1\oplus x_7=y_3\ u_5=u_4\oplus x_8=y_1\ u_6=u_1\oplus u_3=y_2\ \end{array} $$
感謝您的任何建議。
**編輯：**正如親愛的 fgrieu 帶著貪婪的想法所說，答案如下： $$ \begin{array}{l}\tag{3} u_1=x_2\oplus x_8=y_4\ u_2=x_1\oplus u_1\ u_3=u_2\oplus x_7=y_1 \ u_4=u_2\oplus x_6=y_2\ u_5=u_3\oplus x_8=y_3 \end{array} $$
感謝貪婪的想法。
是的。我有一個解決方案 5 $ \oplus $ .
提示 1：這不適用於 $ * $ （普通乘法，甚至是乘法 $ \Bbb Z^*_p $ ) 哪裡有 $ \oplus $ ，因為我們必須使用 $ \oplus $ 那 $ * $ 不具有。
提示 2：正確的路徑是貪婪的。
提示 3：計算的關鍵 $ y_3 $ 遲到了，只需多走一步。