如何結合nnn“更少隨機”位生成一個“更多隨機”位？

假設我們有一個隨機數生成器badrand()以1機率生成 $ 0.9 $ 並且0很有可能 $ 0.1 $ .

我們如何結合 $ n $ 位從badrand()獲得一點betterrand()？它給出0or的機率是1多少？

我認為這是可能的，因為組合輸出的熵隨著每次呼叫而增加badrand()。如果我錯了，請指導我。

這很常見且易於修復。雖然這是一個非常糟糕的 RNG :-)

在計算能力非常小的情況下（例如 Arduino Uno），我們將按照其他答案通過馮諾依曼技術提取

$$ see note though $$. 對於更大的設備（例如 ARM、Snapdragon 和更大的設備），我們利用剩餘雜湊引理(LHL)。這允許提取 $ O(1) $ 時間。 鑑於不存在純粹的隨機性（它總是 $ \epsilon $ 遠離公正），我們從 LHL 知道 $ \epsilon = 2^{-(sn-k)/2} $ . 然後我們：-

1. 選擇一個可接受的偏差，比如說 $ \epsilon = 2^{-64} $ 根據 NIST 的建議。
2. 選擇一個雜湊函式作為主要的隨機提取器，比如 SHA-256，這樣我們就可以利用 CPU SHA 擴展來提高速度。
3. 求解 LHL 公式使我們確定雜湊函式的輸入位長度應為2527位，因為您的badrand()min.entropy ( $ H_{\infty} $ ) 為0.152位/位。
4. 因此最終的熵偏差將是 $ (1-\frac{1}{2^{64}}) $ 比特/比特。
5. 將其轉換為機率偏差， $ P(x_i = 0, x_i = 1) \approx 0.5 \pm 2^{-66} $ .

---

注意：馮諾依曼絕對要求輸入流是不相關的。如果它具有自相關（通常 $ R > 10^{-3} $ )，提取技術不合適。LHL 沒有這樣的限制。它只需要測量 $ H_{\infty} $ so 更靈活，儘管它具有更高的計算元素，僅適用於更大的處理器。

引用自：https://crypto.stackexchange.com/questions/89160