# Proving G(x)=x||[x^2 mod 2^N] is not a PRG

This was a question from my exam yesterday. We have that $$G:\{0, 1\}^n\rightarrow \{0, 1\}^{2n}$$ and $$G(x)=x\mathbin\|[x^2 \bmod 2^n]$$ with $$x$$ is uniform and $$|x|=n$$, give an efficient distinguisher $$D(w)$$ that shows that $$G(x)$$ is not a PRG.

After writing a program that shows all values $$[x^2 \bmod 2^n]$$ can take for some fixed $$n$$, I found that there is a mirror pattern in these values, but I don't see how to mathematically prove this.

• By mirror pattern, do you mean that $x^2 \equiv (2^n-x)^2 \pmod{2^n}$? That's easy to show; $(2^n-x)^2 \equiv (-x)^2 \equiv (-1)^2x^2 \equiv x^2$ Oct 22, 2020 at 13:20

## 1 Answer

Given as input a $$2n$$-bit string $$x||y$$, the distinguisher $$D(x||y)$$ outputs 1 if $$y = x^2 \bmod{2^n}$$ and $$0$$ otherwise.

If $$x||y$$ is uniformly distributed over $$\{0,1\}^{2n}$$, the probability that $$y=x^2 \bmod{2^n}$$ is $$2^{-n}$$. If $$x||y$$ is distributed as $$G(X)$$ where $$X$$ is uniform over $$\{0,1\}^n$$, the probability that $$y=x^2 \bmod{2^n}$$ is 1. The distinguishing advantage of $$D$$ is $$1-2^{-n}$$, which is non-negligible.