1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (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. $\endgroup$ – usul Jun 27 '14 at 13:25
  • $\begingroup$ @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? $\endgroup$ – vnm Jun 30 '14 at 21:12
1
$\begingroup$

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.

So the answer to question B is that this nesting trick does not increase randomness, it can only decrease it. There is no deterministic procedure that can increase randomness.

Hope this helps

$\endgroup$
  • $\begingroup$ Thanks for the answer. I am not sure though about the last paragraph: isn't a PRNG by definition a deterministic procedure which increases randomness? $\endgroup$ – vnm Jun 30 '14 at 21:20
  • $\begingroup$ PRNGs produce numbers that look random but the only true randomness is in the seed. If you know the seed that was used, you can guess all the values that the PRNG will output. So it doesn't increase randomness since guessing the output of the PRNG is at most as hard as guessing the seed. $\endgroup$ – Philippe Lamontagne Jul 1 '14 at 15:50
  • $\begingroup$ I think I used the word 'randomness' but I should have be more precise and rather use "apparent randomness". My question was if the "apparent randomness" of the PRNG can be increased or not using the nesting trick. Or, to put it in another way, if we can produce a better (in some sense) PRNG by using the nesting trick. $\endgroup$ – vnm Jul 19 '14 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.