證明 G(x)=x||X2模數_2ñX2米○d2ñx^2 mod 2^N不是PRG

這是我昨天考試的一道題。我們有那個 $ G:{0, 1}^n\rightarrow {0, 1}^{2n} $ 和 $$ G(x)=x\mathbin|[x^2 \bmod 2^n] $$和 $ x $ 是均勻的並且 $ |x|=n $ ，給出一個有效的區分器 $ D(w) $ 這表明 $ G(x) $ 不是PRG。

編寫顯示所有值的程序後 $ [x^2 \bmod 2^n] $ 可以採取一些固定的 $ n $ ，我發現這些值中有一個鏡像模式，但我不知道如何在數學上證明這一點。

給定作為輸入 $ 2n $ -位串 $ x||y $ , 區分器 $ D(x||y) $ 輸出 1 如果 $ y = x^2 \bmod{2^n} $ 和 $ 0 $ 否則。

如果 $ x||y $ 均勻分佈在 $ {0,1}^{2n} $ , 的機率 $ y=x^2 \bmod{2^n} $ 是 $ 2^{-n} $ . 如果 $ x||y $ 分佈為 $ G(X) $ 在哪裡 $ X $ 是統一的 $ {0,1}^n $ , 的機率 $ y=x^2 \bmod{2^n} $ 是 1. 的顯著優勢 $ D $ 是 $ 1-2^{-n} $ ，這是不可忽略的。

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