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

Question

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.

Answer 1

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.