# What is and amplification factor in pseudo-random generators?

I can't seem to find an answer to this. For instance, I have this question:

Show that, if $$P=NP$$, there aren't any pseudo-random generators (even with amplification factor $$n+1$$).

My gut tells me this is because, in a world where $$P=NP$$, pretty much any process can be efficiently inverted so there aren't one-way functions (which pseudo-random generators rely on).

Let $$G:\{0,1\}^*\rightarrow\{0,1\}^*$$ be a PRG that maps strings of length $$n$$ to strings of length $$l(n)$$, then $$l(n)$$ is said to be the stretch function of $$G$$. If $$l(n)>n$$ and $$l$$ is injective, then you have $$\forall n :|Im(G)\cap\{0,1\}^n|\le 2^{n-1}$$. You can use this to construct a language $$L\in NP$$, such that $$L\in P$$ allows you to break $$G$$ (construct a distinguisher with success probability $$\ge\frac{1}{2})$$. Note that you can relax the injectivity requirement by ignoring some of the output (i.e. given a PRG with stretch $$l(n)>n$$, you can construct a PRG with stretch $$l'(n)=n+1$$).
• I'm having trouble understanding this expression: $\forall n :|Im(G)\cap\{0,1\}^n|\le 2^{n-1}$. What is $Im$ in this context? – Pedro Costa Jun 17 at 9:49
• The image of $G$ – Ariel Jun 17 at 10:01
• Then isn't $Im(G)\cap\{0,1\}^n = \emptyset$ since $Im(G)$ has outputs with size $n+1$ (considering the example I gave) and $\{0,1\}^n$ has outputs with size $n$. So, let's say, isn't $000$ considered different from $00$? – Pedro Costa Jun 17 at 11:13
• $Im(G)$ is the image of $G$ as a function from $\{0,1\}^*$ to $\{0,1\}^*$, you were talking about $Im\left(G|_{\{0,1\}^n}\right)$ – Ariel Jun 17 at 11:14
• But you said $G$ maps strings of length $n$ to strings of length $l(n)$. So in that case, won't $Im(G)$ have outputs with size $l(n)$? – Pedro Costa Jun 17 at 11:17