\newpage\subsection{Pseudo-randomness.\label{pseudor}} The above definition of randomness is very robust, if not practical. True random generators are rarely used in computing. The problem is {\em not} that making a true random generator is impossible: we just saw efficient ways to perfect the distributions of biased random sources. The reason lies in many extra benefits provided by pseudorandom generators. E.g., when experimenting with, debugging, or using a program one often needs to repeat the exact same sequence. With a truly random generator, one actually has to record all its outcomes: long and costly. The alternative is to generate {\em pseudo-random} strings from a short seed. Such methods were justified in [Blum Micali], [Yao]: First, take any one-way permutation $F_n(x)$ (see sec.~\ref{crypt}) with a {\em hard-core} bit (see below) $B_p(x)$ which is easy to compute from $x,p$, but infeasible to guess from $p,n,F_n(x)$ with any noticeable correlation.\\ Then take a random {\em seed} $x_0,p,n\in\{0,1\}^k$ and Repeat: ($S_i\gets B_p(x_i);\, x_{i+1}\gets F_n(x_i);\, i\gets i+1$). We will see how distinguishing outputs $S$ of this generator from strings of coin flips would imply a fast inverting of $F$ (believed impossible). But if P=NP (a famous open problem), no one-way $F$, and no pseudorandom generators could exist. By Kolmogorov's standards, pseudo-random strings are not random: let $G$ be the generator; $s$ be the seed, $G(s) = S$, and $\|S\|\gg k=\|s\|$. Then $K(S) \le O(1)+ k \ll \|S\|$, so this violates Kolmogorov's definition. We can distinguish between truly and pseudo- random strings by simply trying all short seeds. However this takes time exponential in the seed length. Realistically, a pseudo-random string will be as good as a truly random one if they can't be distinguished in feasible time. Such generators we call {\em perfect}. {\bf Theorem}: [Yao] Let $G(s)=S\in\{0,1\}^n$ run in time $t_G$. Let a probabilistic algorithm $A$ in expected (over internal coin flips) time $t_A$ accept $G(s)$ and truly random strings with different by $d$ probabilities. Then, for random $i$, one can use $A$ to guess $S_i$ from $S_{i+1},S_{i+2}, \ldots$ in time $t_A+t_G$ with correlation $d/O(n)$. Proof: Let $p_i$ be the probability that $A$ accepts $S=G(s)$ modified by replacing its first $i$ digits with truly random bits. Then $p_0$ is the probability of accepting $G(s)$ and must differ by $d$ from the probability $p_n$ of accepting random string. Then $p_{i-1}-p_i = d/n$, for randomly chosen $i$. Let $P_0(x)$ and $P_1(x)$ be the probabilities of acceptance of $r0x$ and $r1x$ for random $r$ of length $i-1$. Then $(P_1(x)+P_0(x))/2$ averages to $p_i$ for $x=S_{i+1}, S_{i+2},\ldots$, while $P_{S_i}(x)=P_0(x)+(P_1(x)-P_0(x))S_i$ averages to $p_{i-1}$ and $(P_1(x)-P_0(x)) (S_i-1/2)$ to $p_{i-1}-p_i = d/n$. So, $P_1(x)-P_0(x)$ has the stated correlation with $S_i$. Q.E.D. If the above generator was not perfect, one could guess $S_i$ from the sequence $S_{i+1},S_{i+2},\ldots$ with a polynomial (in $1/\|s\|$) correlation. But, $S_{i+1}, S_{i+2}\ldots$ can be produced from $p,n,x_{i+1}$. So, one could guess $B_p(x_i)$ from $p,n,F(x_i)$ with correlation $d/n$, which cannot be done for hard-core $B$. \paragraph {Hard Core.} The key to constructing a pseudorandom generator is finding a hard core for a one-way $F$. The following $B$ is hard-core for any one-way $F$, e.g., for Rabin's OWF in sec.~\ref{crypt}. [Knuth 1997, v.2, 3d ed., Chap.3.5.F Pseudorandom numbers, pp.36, 170-179] has more details and references. Let $B_p(x)=(x\cdot p)= (\sum_ix_ip_i\bmod2)$. [Goldreich Levin] converts any method $g$ of guessing $B_p(x)$ from $p,n,F(x)$ with correlation $\varepsilon$ into an algorithm of finding $x$, i.e.\ inverting $F$ (slower $\varepsilon^2$ times than $g$). {\bf Proof.} Take $k=\|x\|=\|y\|$, $j=\log(2k/\varepsilon^2)$, $v_i= 0^i10^{k-i}$. Let $B_p(x) =(x\cdot p)$ and $b(x,p)=(-1)^{B_p(x)}$. Assume, for $y=F_n(x)$, $g(y,p,w)\in\{\pm 1\}$ guesses $B_p(x)$ with correlation $\sum_p2^{-\|p\|}b(x,p) g_p >\varepsilon$, where $g_p$ abbreviates $g(y,p,w)$, since $w,y$ are fixed throughout the proof. Averaging $(-1)^{(x\cdot p)} g_p$ over $>2k/\varepsilon^2$ random pairwise independent $p$ deviates from its average by $<\varepsilon$ (and so is $>0$) with probability $>1-1/2k$. The same for $(-1)^{(x\cdot[p+v_i])} g_{p+v_i}= (-1)^{(x\cdot p)} g_{p+v_i} (-1)^{x_i}$. Take a random matrix $P\in\{0,1\}^{k\times j}$. Then the vectors $Pr$, $r\in\{0,1\}^j\setminus\{0^j\}$ are pairwise independent. So, for a fraction $\ge1-1/2k$ of $P$, sign$\sum_r (-1)^{xPr} g_{Pr+v_i}= (-1)^{x_i}$. We could thus find $x_i$ for all $i$ with probability $>1/2$ if we knew $z=xP$. But $z$ is short: we can try all $2^j$ possible values! So the inverter, for a random $P$ and all $i,r$, computes $G_i(r)=g_{Pr+v_i}$. It uses Fast Fourier on $G_i$ to compute $h_i(z)=\sum_rb(z,r)G_i(r)$. The sign of $h_i(z)$ is the $i$-th bit for the $z$-th member of output list. Q.E.D.