Are some pseudorandom number generators unpredictable?by bbbeard Tags: generators, number, pseudorandom, unpredictable 

#1
Nov611, 01:23 AM

P: 192

The topic here is pseudorandom 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 LuscherMarsagliaZaman PRNG is, because it actually updates some number of registers N>>1 at each step and only outputs a 32bit 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 randomish outputs in the course of doing its work. Is there a name for this class of PRNG? BBB 



#2
Nov611, 09:00 AM

Homework
Sci Advisor
HW Helper
Thanks ∞
PF Gold
P: 11,025

What is the difference between a pseudorandom number generator and an actual ideal random number generator?
You get intrinsic unpredictability where you don't know the algorithm  like if you take the lowest placevalue number in a rapidly changing natural measurement like wind speed as part of your number generation. The size of the output you need before you can work out the seed is a measure of the randomness of the generator (iirc). 



#3
Nov611, 09:21 AM

Sci Advisor
P: 3,175





#4
Nov811, 03:33 PM

P: 192

Are some pseudorandom number generators unpredictable?In my own coding I have abused the LMZ generator by seeding it with a single 32bit seed, which I used to seed the system call to fill the 24 registers. This means I only generated 2^32 different series of numbers, instead of a potentially much larger space, But for what I was doing that was sufficient. My question is really just a curiosity about whether there is a difference between linear congruential generators (where the current output tells you all you need to know to predict the future outputs) and other PRNGs. As far as I know, all useful PRNGs have the property that if you know the seed(s), you can reproduce the entire sequence of outputs, and obviously there are PRNGs where knowing the current output lets you predict future outputs without knowing the seeds. But I'm wondering if there are PRNGs where knowing N consecutive outputs is still not enough to predict future outputs, for any N. BBB 



#5
Nov811, 03:41 PM

P: 192




Register to reply 
Related Discussions  
computing with random generators (MATLAB)  Math & Science Software  4  
Single or multiple random number generators?  Programming & Computer Science  1  
Random Number Generators and ESP  General Discussion  3  
Pseudo random number algorithm  Set Theory, Logic, Probability, Statistics  0  
blackjack, random number generators...  Set Theory, Logic, Probability, Statistics  2 