Seeding a random number generator with a RNG

[ftg]

There is serious research on this subject in Computer Science. It has actually been presented in papers methods where you can start with a smallish random seed to generate a very large “cryptographically secure” large random sequence.

Note that the laws of randomness as used in this context means that there is no way the result is any more random than the input, but it is in some way provably less “pseudorandom” than what people are talking about here. I.e., you can generate stuff practically as good as one-time-pads using random keys a lot shorter than the message length. (But they have other nice applications.)

If you want to read such papers, I suggest the conference proceedings from The ACM Symposium on Theory of Computing or IEEE Foundations of Computer Science from about 1994 or so if my memory is correct as to when these results first came out.

[Desmostylus]

Randomness can be improved by using more than one pseudo-random number generator, but not by using one to seed the other.

I don’t have a copy of Knuth handy, but here’s a second hand quote from Press, Flannery et al:

RAN1 is based on three linear congruential generators from the above table. One generator is used for the most significant part of the output number, the second for the least significant part, and the third to control a shuffling routine (here absolutely essential because of the relatively small values of the multiplier m available to us). The shuffling routine… is one which has been suggested by Knuth and widely used. RAN1 is, of course, very much better than any of its three generators individually: its period is (for all practical purposes) infinite, and it ought to have no sensible sequential correlations. The choice of which constants from the accompanying table to use is arbitrary, as is the length of the shuffling array.

[Desmostylus]

That should read “second hand cite, in this quote…”

[Shalmanese]

Uhm, its actually suprisingly hard to think up a “good” random number generating algorithm. Paradoxically, making things more complicated quite often makes it WORSE, it some cases, much, much worse. I can guarentee that double seeding is provably no better than a good single seeding algorithm and can be worse depending on how it is implemented.

[Desmostylus]

*Originally posted by Shalmanese *
**Uhm, its actually suprisingly hard to think up a “good” random number generating algorithm. Paradoxically, making things more complicated quite often makes it WORSE, it some cases, much, much worse. I can guarentee that double seeding is provably no better than a good single seeding algorithm and can be worse depending on how it is implemented. **

I’m finding this a bit hard to follow, Shalmanese.

What do you mean by “random number generating algorithm”? A truly random generator or a pseudo-random generator?

And I’m unfamiliar with the term “double seeding”. What’s that mean?

[Desmostylus]

*Originally posted by Desmostylus *
**And I’m unfamiliar with the term “double seeding”. What’s that mean? **

Forget that. I assume you just mean “Seeding a random number generator with a RNG”.

[dtilque]

*Originally posted by Pleonast *
(In fact, simply adding the outputs of two RNGs will typically generate a RNG with a cycle length equal to the product of the two cycle lengths.)

Adding two random number will give a random number with a different probability distribution. Example: one six sided die produces a random integer between 1 and 6 with a flat distribution. Adding the output of two dice produces a random number between 2 and 12 with a bell shaped distribution.

To extend the cycle length with more than one RNG and without changing the probability distribution[sup]1[/sup], simply alternate between the RNGs. The cycle length will then be the number of RNGs times product of all the cycle lengths divided by the greatest common divisor of the cycle lengths.
[sup]1[/sup] This assumes all RNGs have the same distribution.