Well, I’m definitely no expert in number theory or cryptography, but is there any broad knowledge out there on the effects of “randomness” of a pseudorandom number generator being improved by seeding said number generator with a pseudorandom number?
Is this asking what happens when you seed a PRNG with a PRNG?
A particular number is not random, or pseudorandom. Those are properties of sequences of numbers.
You probably wouldn’t get much of anything, since they would still be drawing from the same initial seed, most likely the oscillations of the system clock. It would be like squaring a number, except in PRNG terms.
No expert either, but as I understand it, you still gotta seed the first generator to get your first pseudorandom number.
So say you Seed it with 18, and it returns back 526.
In effect, you’re now not seeding the second generator with a random number, you’re seeding it with 526* which is a real hard number.
You could seed the first one with something that won’t be repeating (For example, the number of seconds your system has been turned on, or whatever “tick count” the OS you’re using will give you) and then you’re putting a “semi-random” seed into your first generator, which gives you back some number, which you use to seed the second one…
But you’ve gone through the steps of getting that tick count, so why the second step? If you just use one RNG, and it’s a well written one, then seeding it with the tick count should be sufficent to return a decent random number.
Steve
*I know, most RNGs return a floating point between 0 and 1, not an integer like 526…but that was just for example, since many of the RNGs I’ve used need an integer as the seed.
Oh right. Duh.
What I really meant to ask was, is there a way to improve the randomness of a pseudorandom sequence of numbers by nesting PRNGs in some way?
I think that you are asking that if you layer (nest) the PRNG that cracking it would be harder because of the # of times (degrees of randomness) someone had to delve into it. Am I correct?
:BTW I don’t want a Kevin Bacon hijack::eek:
It won’t make any difference. All that matters is the sequence of numbers generated, not how it was seeded. For a good PRNG, all seeds should give approximately the same degree of randomness.
Simply seeding a second RNG with a number generated by the first will not improve the net “randomness” of the output. There are more complicated schemes that will improve the output.
For example, use the first RNG to fill a table with pseudo-random numbers. Then, use the second RNG to choose which table entry to return. Finally, replace the used entry with a new number generated by the first RNG. Repeat as needed.
This process is basically using the second RNG to choose the output order of the first. This should help remove any correlations in the first RNG. It works much better if the two RNG use completely separate algorithms (e.g., one is linear congruential and the other a differential Fibonacci sequence).
**This is where I say, “dammit, 100 people already said that!” **
And this is where I say, “Thanks! That answers my question perfectly!”
But once again, I have not asked what I meant to ask. What I really want to know is, is there a firm theory behind this “propagation of randomness”, or should I say, “dissipation of correlation”? I mean, suppose you can define a metric space of PRNGs based on their correlation/randomness. Is there theory behind some sequence that you might generate by iterating this “random table” scheme? Would it have correlation limit 0? If you were iterating with two PRNGs, can you give the resulting correlation in terms of the correlations of the original two PRNGs? Will the combined correlation ever be greater than the greater of the two original correlations?
This is where I say “heck if I know”.
I do know that the table indexing scheme will in general multiply the cycle lengths. So if the first RNG has a cycle length of N (i.e., it starts repeating after outputing N numbers), and the second has a cycle of M, the table output will have a cycle length of NM (the product of the cycle lengths).
My caveat is I don’t know all the conditions necessary for this to be true. Certainly, if you read the literature and pick two RNGs generally considered “good”, the table output will be much better than either alone. (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.)
I remember when I was coding something once and I seeded a random number generator with another random number generator, hoping for a more random number I suppose. The end result was that the program gave me the same output every single time I ran it.
:smack:
You have to be very careful when dealing with psuedorandom numbers. That “psuedo” part can really bite you if you’re not careful.
What if we modified Pleonast’s table idea. We start by seeding a PRNG with some real world “random” value such as the full system date and time or the speed of keyclicks or mouse movent or something similar. Then we fill in a large table with the values generated by the PRNG. Then, rather than using a second PRNG we use the same real world “random” generator (or a different one) to pick values from the table. As we use values we replace them with others from the original PRNG. This way we have a random distribution (depending of course on the quality of the original PRNG) with no cycle (I think…).
Linux has a device (/dev/random) that generates “real” random bits. A program can open the device as a file and read random data from it.
There are two problems with your idea, davidm. The first is that random data is generated very slowly by a computer. I don’t have any numbers, but at much slower rate than what most applications need.
The second problem is that many applications need reproducible “random” numbers. Cryptography obviously needs to be able to invert the process to recover the plaintext. Scientific and engineering applications often need to control for the effects of the randomness. (For example, run a simulation with a given random number sequence, then make a change and run it again with the same sequence. Thus any differences will be due to the change and not because a different random number sequence was used.)
These problems can be partially compensated by using the real random number as a seed for the RNG. The idea is to in effect increase the randomness produced by the real RNG. But your random numbers are still only as good as your RNG; it’s just that you’re starting in an unpredictable location in the RNG’s cycle.
For a more familiar example: Many simple computer games use reproduceable random numbers. Nobody actually went through and created 32,000 different FreeCell games by hand; the game number is used as the seed for the PRNG that “shuffles” the cards. Put in the same game number, and you’ll always get the same game, without your computer actually having to memorize the setup for thousands of different games.
Whether or not there are problems with it depends on the application. My intent was to find a way to generate a non-reproducible stream of values with a random distribution. Up till now no one had mentioned reproducibility. If you want something that is reproducible then obviously my method wouldn’t be appropriate. As far as the speed of generation goes, it again depends on the application. Some apps may only need a new value every few seconds. Some apps may be able to work from a pre-generated list of numbers (you could also do this when reproducibility is required). And there are probably real world sources that could generate a stream of values very rapidly. You might be able to use a photon detector and count the time between hits, for example.
And it doesn’t just start at an unpredictable location in the PRNG’s cycle. Every value comes from an unpredictable location if you choose the proper source and use it wisely. Only in the worst case, where you end up choosing from the same slot every time, would it degenerate to being the same as using the PRNG alone.
This originally made me cringe, because I thought that you meant that the “random” generator would generate a sequence of random numbers, which would solve the problem on its own.
Upon reading it, I think you just meant some sequence generated by human entropy. This is very interesting, because supposedly humans make bad RNGs when they are trying to act randomly (delve into the frightening world of rock, paper, scissors: http://www.worldrps.com/ ). However, they may do a lot better when they AREN’T trying to be random… which raises another interesting question. Maybe we can make a random number generator forum on the SDMB.
Your method will certainly work for some applications. However, for those applications it’s probably simpler just to use your random number source directly, instead of using it to index a pseudo-RNG.
/dev/random does a fairly good job at taking random user input (key timing, mouse motions, etc.) and making a random number sequence from it. It’s main drawback is that it’s slow.
Actually this is quite simple. Just write a script to download a page that changes frequently (e.g. http://boards.straightdope.com/sdmb/forumdisplay.php?s=&forumid=3 ). Then calculate a hash value (e.g., MD-5 or SHA-256). A hash takes all the bits of the input, scrambles them, and outputs a smaller, fixed-length value. Any small change in the input is very likely to produce a large, unpredictable change in the output value. Use this hash value to seed your favorite RNG.
Hmm, I wonder if anyone has considered using websites as an entropy source for /dev/random…
I of course meant that you would use something unintentional, like the time between keyboard clicks while typing or mouse double-clicks or something similar. Even if a person tried to time this, you could measure it to a precision beyond that which a person could control. I can recall using a commercial piece of software that specifically instructed the user to type or move and click the mouse randomly until a progress bar was full in order to generate a seed. I would never suggest that you should have a human attempt to consciously create a list of random numbers. That would obviously never work!
I can make a sequence of random numbers!
… 1 …
DAMMIT!