使用相同輸入的 PRG 連接仍然是 PRG 嗎？
假設我們有一個安全的 PRG $ G: {0,1}^s→ {0,1}^n $ 我們定義一個 $ G’(k) $ 作為：
$$ G’(k) = G(k) | G(k) $$
因此，如果 $ G(k)=\mathbf{i} $ , $ G’(k) = \mathbf{i} | \mathbf{i} $
是 $ G’ $ 仍然是一個安全的 PRG？
根據我自己的理解應該是，因為統計區分器會產生相同的零和一的類比，因此 $ G’ $ 也應該是一個安全的 PRG。
有沒有關於 PRG 的其他原則？ $ G’ $ 不滿足？
參考這篇文章
如果我們打電話 $ U_k $ 隨機變數均勻分佈在長度為的位串上 $ k $ ，然後是一個函式 $ g: {0,1}^k \to {0,1}^m $ 如果沒有可行（多時間，如果你想）算法可以區分，則稱為偽隨機生成器 $ g(U_k) $ 和 $ U_m $ 以不可忽略的機率。
更正式地讓 $ U’_m = g(U_k) $ 那麼任何區分器有效的區分優勢 $ D $ 我們表示為 $ \Delta^D(U’_m, U_m) = \Pr^{DU_m}[Z = 1] - \Pr^{DU’_m}[Z = 1] $ 可以忽略不計。
這裡 $ Z $ 是區分器的輸出，任何合適的“非常小”的概念都可以忽略不計；效率相同。
現在我區分的能力 $ U_k $ 從你的 PRNG $ g: {0,1}^k \to {0,1}^m \mathbin| {0,1}^m $ 顯然是微不足道的。因為您的發電機的任何輸出都具有對稱性，如果我看到這種對稱性，那麼正在使用的發電機很可能就是您的發電機。
請注意，對於 $ G : {0,1}^s \to {0,1}^{n} $ 成為PRG， $ n $ 必須是的多項式 $ s $ ，所以讓我們將其重寫為 $ G : {0,1}^s \to {0,1}^{\ell(s)} $ ， 在哪裡 $ \ell(s) $ 是多項式。
反駁你的命題 $ G’ : {0,1}^s \to {0,1}^{2\cdot\ell(s)} $ 是一個 PRG，它足以展示一個機率多項式時間算法（超過 $ s $ ) 那，對於隨機 $ k $ , 區分 $ G’(k) $ 從一個隨機的位串中抽取 $ {0,1}^{2\cdot\ell(s)} $ 以不可忽略的機率。給定一個字元串 $ x \in {0,1}^{2\cdot\ell(s)} $ ，這是一種這樣的算法，它執行的時間與 $ 2\cdot\ell(s) $ :
- 分裂 $ x $ 長度—— $ n $ 一半 $ x_1 $ , $ x_2 $ 這樣 $ x_1 | x_2 = x $ ;
- 如果 $ x_1 = x_2 $ ，然後輸出
True；否則，輸出False。如果 $ x $ 由 $ G’ $ , 那麼這個算法保證輸出
True. 如果 $ x $ 是隨機的，它輸出的機率True是 $ 2^{-\ell(s)} $ . 因此，顯著的優勢是$$ 1 - 2^{-\ell(s)} $$
這不是一個可以忽略的函式 $ s $ . 所以 $ G’ $ 不是PRG。
用更簡單的英語來說，檢查輸入的前半部分是否與後半部分相同的統計測試總是在輸出上成功 $ G’ $ .