Skip to main content
1 of 7
Diagon
  • 193
  • 1
  • 7

@Bush Look at the definition of a PRG, here: https://en.wikipedia.org/wiki/Pseudo_random_number_generator#Mathematical_definition

This basically says that a PRG produces a "scatter" of points on the image set that approximates the uniform distribution. More precisely, if we consider a set E in the image set of the PRG, then the measure of set of points that the PRG maps into E is very close to the measure of E.

So, let's suppose we have a PRG F: DF -> I.

Define a new function G: DG -> I, st. G(2n)=F(n) and G(2n+1) = F(n).

Notice that:

(1) F([|k/2|]) = g(k), where [|x|] is the greatest integer <= x.

(2) |DG| = 2|DF|, where |S| is the number of points in the set S.

For a set E on the image space, the number of points that map into it via G is just 2x the number of points that map into it by F. On the other hand, the domain of G is twice as big as the domain of F. So the measure of the preimages via F and G are the same. So, if F approximates the uniform distribution on I, then so does G. Therefore, if F is a PRG, then so is G.

Diagon
  • 193
  • 1
  • 7