將 256 位隨機數映射到 3 位數字
我正在製作一個執行 n 輪的 2 人骰子遊戲。使用從 randao 理解的概念來創建隨機骰子角色。
每個使用者遞歸地生成隨機種子的 n sha3 散列：例如
H[0] = sha3(sha3(seed)) H[1] = sha3(sha3(H[0])) ... H[n] = sha3(sha3(H[n-1]))在這
nth一輪中，我們xor將H[nth]每個使用者的值用作該輪的隨機值：random_result
random_result我的問題：在不完全破壞熵的情況下將 256 位映射到 6 面骰子的最佳策略是什麼？
方法 1 - 大整數數學
將 256 位轉換
random_result為無符號大整數。除以 6 並取餘數。你的擲骰結果是餘數加一。6 $ 6 $ 不均分2256 $ 2^{256} $ . 它分為大約1.93×1074 $ 1.93\times10^{74} $ 時間與精確的餘數4 $ 4 $ . 這意味著價值觀1 $ 1 $ -4 $ 4 $ 被過度代表，但數量可以忽略不計，因為它們只代表一次以上5 $ 5 $ 和6 $ 6 $ 在一個巨大的範圍內。
對低模輥的偏向遠小於2−128 $ 2^{-128} $ ，現代密碼學對最大可檢測機率偏差量的稍微隨意的門檻值。
方法 2 - “小”整數數學
讓米=6×Fl○○r(232÷6)=4294967292 $ M = 6 \times floor(2^{32} \div 6) = 4294967292 $ ， IE。適合 32 位無符號整數的 6 的最大倍數。
將 256 位拆分為 8 個 32 位無符號數。找到小於這些值的第一個值米 $ M $ 並返回一個加上其值除以 6 的餘數。此返回值具有一個值範圍的值[1,6] $ [1, 6] $ .
使用範圍內的值的原因[0,米−1] $ [0,M-1] $ 代替[0,232−1] $ [0, 2^{32}-1] $ 是因為後者不是被 6 整除的。前者範圍內的隨機數會導致完全均勻的分佈。
一個 32 位值被拒絕的機率為p=(232−米)÷232≈9.32×10−10 $ p = (2^{32} - M) \div 2^{32} \approx 9.32 \times 10^{-10} $ . 所有 8 都被拒絕p8≈5.66×10−73 $ p^8 \approx 5.66 \times 10^{-73} $ 這是非常不可能的機率。確切的機率恰好是p=2−30 $ p = 2^{-30} $ 和p8=2240 $ p^{8} = 2^{240} $ . 同樣，這小於2−128 $ 2^{-128} $ ，所以你不應該期望它發生。
random_result如果它確實失敗了 8 次，您可以通過與計數器連接的散列得出更多的 256 位數字。或者，如果前 7 個失敗，您可以只使用最後的 32 位值。這種情況發生的機率很小，由此產生的偏差也較小。我指定 32 位數字的原因是為了便於實現和優化。沒有任何加密相關性。64 位數字和 64 位除法也可以，但在某些腳本語言中可能不可用，並且 32 位除法在 32 位和 64 位架構上可能比 64 位除法更快。
您可以使用 3 位塊。然後你可以完全消除除法，因為 6 只除 8 一次。拒絕單個塊發生在1/4 $ 1/4 $ 機會。拒絕85次小於6.7×10−52 $ 6.7 \times 10^{-52} $ 或者2−170 $ 2^{-170} $ .
方法 3 - 播種 PRNG
如果 CS-PRNG 是在標準語言庫或流行的附加庫中實現的，這將非常容易，並且具有與非安全 PRNG 類似的 API。由於統計偽影、狀態空間小、可預測性或缺乏良好的種子算法，使用標準 PRNG 並不適用於每個應用程序。
編輯：避免這種方法。我沒有一個可以舉的例子。有太多可能出錯的方法。
沒有一種方法具有顯著的偏差，因此模輥的熵非常接近日誌26 $ \log_2 6 $ 一點點的熵。（假設熵種子相當高，例如 128 位熵。它不需要 256 位熵。）
我認為您不需要基於熵的答案。我不知道你所說的“搞砸熵”是什麼意思，我想你也不知道。
對於每種方法，您可以通過將雜湊輸出的熵處理為大約等於米一世n(256,種子熵) $ min(256, \text{seed-entropy}) $ 並通過計算有多少雜湊輸出映射到該擲骰值來計算每個結果 1 到 6 的機率。
由於我們已經知道偏差非常小，因此我們知道模卷結果是均勻的。由於它是關於均勻的，我們知道它具有大約可以從 6 元素離散均勻分佈中得到的最大熵，日誌26 $ \log_2 6 $ .