算術和位運算的擴散

October 17, 2022

我想估計不同類型的函式何時以及是否提供完全或部分擴散。
我試圖了解基本操作的擴散，例如：
另外，
乘法，
異靈。
如果我們改變一點 $ a $ 結果平均會改變多少位 $ c $ 如果我們這樣做：
$ a+b \mod n = c $
如果我們改變一點 $ a $ 結果平均會改變多少位 $ c $ 如果我們這樣做：
$ a \oplus b \mod n = c $
如果我們改變一點 $ a $ 結果平均會改變多少位 $ c $ 如果我們這樣做：
$ a \cdot b \mod n = c $
如果我們改變一點點 $ a $ 結果平均會改變多少位 $ c $ 如果我們這樣做：
$ (a >> 1) \cdot b \mod n = c $
推斷是否相當容易，還是我必須編寫一個程序來檢查它？
在異或的情況下，如果我們計算它，只會改變一位 $ a $ 相差一點點。但是其他情況呢？我認為萬一 $ a >> 1 $ 將近一半的位將被更改，因為如果我們以這種方式切換兩個位，我們有大約 50% 的機率它們會相同或不同。很簡單 $ a >> 1 $ 可以提供良好的擴散（如果我們將它與其他混合操作結合起來，只是一遍又一遍地重複這個操作，當然，沒有任何意義）。
編輯：
讓我們考慮一下 $ n $ 等於的冪 $ 2 $ .

您可以使用雪崩圖直覺地檢查不同操作的擴散。
我已經生成了這些操作的雪崩圖，我使用的大小 $ a $ 和 $ b $ 是 64 位。結果也是一個 64 位變數。
我使用的工具會生成所有位變化的圖表，而不僅僅是 $ a $ ，但它仍然應該提供資訊。
的擴散 $ a \oplus b $
如您所料；使用普通 XOR，輸出位 $ c_n $ 僅受輸入位影響 $ a_n $ 和 $ b_n $ . 這就是它的樣子。
的擴散 $ a + b $
略有改進是添加。您可以看到，不是每個位只影響自己，而是現在位周圍有一個非常輕微的擴散。
的擴散 $ a \cdot b $
乘法提供了巨大的改進。但是乘法只會將變化擴散到一個方向。並且根據您所針對的處理器，乘法可能很昂貴或時間不固定。
通過重複簡單的混合器進行擴散
如果你採取一堆可逆的操作來分散變化，並重複執行它們，你可以獲得更好的結果。
下面是一個只有 XOR-shifts 和 add-shifts 的範例。
這是正在執行的操作。正如你所看到的，單獨地沒有一個擴散那麼多，但如果你重複它們，混合會更好。
for (size_t i = 0; i &lt; 4; i++) {
   // Mix a
   a ^= a &gt;&gt; 7;
   a += a &lt;&lt; 13;
   a ^= a &gt;&gt; 9;

   // Mix b
   b ^= b &gt;&gt; 7;
   b += b &lt;&lt; 13;
   b ^= b &gt;&gt; 9;

   // Shift a and b into each other
   u64 a_old = a;
   u64 b_old = b;
   a = (a_old &lt;&lt; 8) | ((b_old &gt;&gt; 56) & 0xFF);
   b = (b_old &lt;&lt; 8) | ((a_old &gt;&gt; 56) & 0xFF);

}

u64 c = a ^ b;