偽隨機發生器
在加密應用程序中，需要兩種類型的（偽）隨機比特流：
- 一條流 $ A= a_{1}a_{2}a_{3}\ldots $ 其中 $ \Pr[a_{i}=0]=\Pr[a_{i}=1]= 1/2\ \forall i $ 和
- 一條流 $ B= b_{1}b_{2}b_{3}\ldots $ 其中 $ \Pr[b_{i}=0]=2/3; \Pr[b_{i}=1]=1/3\ \forall i $ .
提出以下結構：
- 給定一個生成器 $ G_{A} $ 為了 $ A $ , 提出一個有效的結構，使用 $ G_{A} $ 生成 $ B $ .
- 給定一個生成器 $ G_{B} $ 為了 $ B $ , 提出一個有效的結構，使用 $ G_{B} $ 生成 $ A $ .
我不需要這個問題的解決方案。我想知道，如何思考這個問題以獲得解決方案。我知道偽隨機生成器的基本定義。
給出的提示是指無偏算法，這是密碼學的標準答案。但是，對於生成 $ (2/3,1/3) $ 我將在這裡提到的無偏流中的分佈式比特。為清楚起見，呼叫輸出符號 $ a $ 和 $ b $ 和 $ p_a=2/3=1-p_b $ 而不是使用二進制符號
展開以 2 為底的機率得到： $$ \frac{2}{3}=0.101010101010\ldots $$ 和 $$ \frac{1}{3}=0.0101010101\ldots $$ 這意味著這些機率原子具有二元展開式 $$ \frac{2}{3}=\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\cdots=\frac{1/2}{1-{1/4}} $$ 和 $$ \frac{1}{3}=\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\cdots=\frac{1/4}{1-{1/4}} $$ 這種分解會產生以下無限樹，它會生成所需的符號：
如果無偏位為 0，則向左，否則向右，當 $ a $ 或者 $ b $ 再次發出開始；
（第一個左分支應該有符號 $ a $ ).
在 Cover & Thomas 的Elements of Information Theory一書的第 5 章中，證明了這個過程是最優的，即它給出了一個預期最小長度的樹，生成了這個分佈。
**編輯：**正如@supercat 的評論，如果 $ p $ 未知，但輸入位是獨立的，可以分組說 $ 3- $ 元組成兩組所需的機率比，並嘗試最大化實際輸出一個位的機率。 $ k=3 $ 在這種情況下很方便，因為二項式係數 $ \binom{3}{j} $ 能被 3 整除，如果我們忽略第一個和最後一個係數，那麼分組得到一個 $ (1/3,2/3) $ 可能性
$$ when symbols are output $$成為可能。具體來說
如果看到 100 或 011，則輸出 $ b $ . 如果看到 010、001、101 或 110，則輸出 $ a. $ 如果您看到 000 或 111，請扔掉這些位並重試。
