- #1
bbbeard
- 192
- 4
The topic here is pseudo-random number generators (PRNGs), i.e. the kind of algorithm you implement on a computer to do Monte Carlo calculations.
All the PRNGs I know require a "seed" to start a sequence. Given the same seed, the algorithm, which is of course deterministic, will produce the same sequence of numbers.
Some PRNGs have the property that if you know the current output, you can predict what the next output value will be if you know what the algorithm is. I think simple linear congruential generators are in this class.
My question is, are there PRNGs which are not like this? I'm pretty sure there are; I think the Luscher-Marsaglia-Zaman PRNG is, because it actually updates some number of registers N>>1 at each step and only outputs a 32-bit current value. But I think if you know a sufficiently long sequence of outputs, you can reconstruct the contents of the registers, even if you don't know the seed, and then you could predict the next output.
Are some PRNGs intrinsically unpredictable? That is, even given a long sequence of outputs, you cannot predict the next output unless you know the seed? I am imagining some hybrid of RSS encryption and a PRNG -- or maybe mostly just RSS, since it somehow generates random-ish outputs in the course of doing its work. Is there a name for this class of PRNG?
BBB
All the PRNGs I know require a "seed" to start a sequence. Given the same seed, the algorithm, which is of course deterministic, will produce the same sequence of numbers.
Some PRNGs have the property that if you know the current output, you can predict what the next output value will be if you know what the algorithm is. I think simple linear congruential generators are in this class.
My question is, are there PRNGs which are not like this? I'm pretty sure there are; I think the Luscher-Marsaglia-Zaman PRNG is, because it actually updates some number of registers N>>1 at each step and only outputs a 32-bit current value. But I think if you know a sufficiently long sequence of outputs, you can reconstruct the contents of the registers, even if you don't know the seed, and then you could predict the next output.
Are some PRNGs intrinsically unpredictable? That is, even given a long sequence of outputs, you cannot predict the next output unless you know the seed? I am imagining some hybrid of RSS encryption and a PRNG -- or maybe mostly just RSS, since it somehow generates random-ish outputs in the course of doing its work. Is there a name for this class of PRNG?
BBB