"Расширение" генератора псевдослучайных чисел

По генератору $G(x) = g(x)h(x)$ построим $G'(x) = h(x)h(g(x))h(g(g(x)))\ldots$.

Утверждение

Если $G(x)$ - генератор псевдослучайных чисел, то $G'(x)$ - тоже генератор псевдослучайных чисел.

Доказательство

Метод гибридного аргумента: $$G_{k + 1}(x) = h(x)h(g(x))h(g(g(x)))\ldots h(g^k(x))g^{k + 1}(x)$$ $$G_k(x, r_1) = r_1h(x)h(g(x))h(g(g(x)))\ldots h(g^{k - 1}(x))g^{k}(x)$$ $$G_k(x, r_1, r_2) = r_1 r_2 h(x)h(g(x))h(g(g(x)))\ldots h(g^{k - 2}(x))g^{k - 1}(x)$$ $$G_1(x, r) = r_1 r_2 \ldots r_{k + 1} x$$ $$G_0(x, r) = r_1 r_2 \ldots r_{k} h(x)g(x)$$ $G_0$ - истинно случайные биты. $G_k$ - претендент на генератор.

Если $G_{k + 1} = G'$ - не генератор, то $$\exists D\ \exists q(\cdot)\ \forall N\ \exists n > N\ |Pr_{x, r}\{D(G_0(x, r)) = 1\} - Pr_{x, r}\{D(G_k(x, r)) = 1\}| \ge \frac{1}{q(n)}$$ $$\Rightarrow \exists q'\ \forall N\ \exists n > N\ \exists i |Pr_{x, r}\{D(G_i(x, r)) = 1\} - Pr_{x, r}\{D(G_{i + 1}(x, r)) = 1\}| \ge \frac{1}{q'(n)}$$ Тогда $G$ - не генератор:
отличили $$r_1r_2\ldots r_{k - i + 1}h(x)h(g(x))\ldots h(g^{i - 1}(x))g^i(x)$$
от $$r_1r_2\ldots r_{k - i}h(x)h(g(x))\ldots h(g^{i}(x))g^{i + 1}(x)$$

Переобозначим: $y = g^i(x)$, $s = r_1\ldots r_{k - i}$, $T(x) = h(x)\ldots h(g^{i - 1}(x))g^i(x)$.

В этих обозначения мы отличили $sr_{k - i + 1}T(x)$ от $sh(x)T(g(x))$.

Фиксируя $s$, отличили $rT(x)$ от $h(x)T(g(x))$. $$D'(x, r) = D(s r T(x))$$ $D'$ будет отличать $xr$ от $g(x)h(x)$. Это приводит к противоречию с тем, что $g(x)h(x)$ - генератор псевдослучайных чисел.