# nested pseudorandom generator

Suppose we have a pseudorandom number generator PRNG with number of possible seed states K. Let us denote PRNG(k) the number yielded by the generator when the seed state is k. Here k is an integer between 1 and K.

Question A: Is it possible to adapt PRNG to yield pseudorandom integer numbers uniformly distributed between 1 and K?

Assuming that the answer to this question is yes, let's denote by PRNG(k; 1, K) the number between 1 and K yielded by the adapted PRNG when the seed state is k.

We can then build a new pseudorandom number generator by nesting PRNG, i.e.

newPRNG(k) = PRNG(PRNG(k; 1, K))

Question B: From a theoretical point of view, can we say something about the properties of the new PRNG? In particular, does this nesting trick increase or decrease the randomness of the generator, in some sense? I think this question is a natural one but I didn't find any answer on the web.

• (Mainly for question B) Are you picturing PRNG working like this? It has an internal state, is initially seeded, then produces a sequence of pseduorandom numbers in $\{1,...,K\}$, producing one such number and updating its state each time it is called. – usul Jun 27 '14 at 13:25
• @usul Actually in my view of PRNG the internal state and the seed coincide. Basically, there exists a function f such that: if the random seed is k and we ask the PRNG for a number then it yields a number f(k) and automatically update the seed to k+1. If at a later time we ask the PRNG for another number, it yields f(k+1) and update the seed to k+2. When the seed reaches the maximum K it restarts from zero. Is this view too simplistic and naive? – vnm Jun 30 '14 at 21:12

Regarding question A, it is possible to adapt the PRNG to yield uniformly distributed numbers using this. However, the range of this new uniform generator has size smaller than $K$, unless the PRNG is itself uniform. The number of possible outcomes of this new generator will depend on the min-entropy of the original generator.
To get some intuition on why this is so, try to view the problem from an adversarial point of view where the goal is to guess the outcome of the PRNG. If $P_{guess}>1/K$ is the probability of the most probable outcome of the PRNG, then there is no deterministic way to lower the adversary's guessing probability without adding randomness. Therefore if you are to transform the outcome to a uniform distribution then all the equaly likely outcomes must happen with probability at least $P_{guess}$, so there can be at most $1/P_{guess}$ outcomes. Of couse, I'm assuming that the adversary knows the deterministic procedure that is applied, as is usually the case in cryptography.