Random numbers

[mary_201091]

Hi, if I have a sequence of 1000 random numbers generated by a routine similar to rand(), how can i calculate the next 10 numbers of the sequence?

Thanks a lot

[Skizmo]

Your post makes no sense at all. If you have generated 1000 numbers, and you need the next 10, why don't you generate 1010 numbers ?

[hoxsiew]

I think the OP wants to try and determine the state of an unknown PRNG given a sequence of values produced from the RNG. This comes up in cryptanalysis.

See:

http://en.wikipedia.org/wiki/Pseudor...mber_generator

for some refs.

[mary_201091]

Yes, i would like to know the next 10 numbers of the sequence, if i only know the first 1000.

[Lindley]

If the random number generator is doing its job well, that shouldn't be possible.

If I had to tackle the problem, I'd probably try a hidden markov model or something similar. Assume a particular algorithm, and then try to discover its parameters. It'd be hard though.

[ovidiucucu]

[ Moved thread ]

[laserlight]

If the random number generator is doing its job well, that shouldn't be possible.

I think that only applies to cryptographically secure PRNGs and "real" RNGs since "normal" PRNGs might not be designed with this in mind, i.e., the generated sequences may pass statistical tests of randomness, but if you know the algorithm and have sufficient knowledge of the previously generated numbers, you might be able to deduce the state of the PRNG.

[Chris_F]

Yes, i would like to know the next 10 numbers of the sequence, if i only know the first 1000.

Well, you need to know the seed value that was used. Then you need to run it 1010 times and take the last 10.

If you need to be able to do this without knowing the seed value, you came to the wrong place. Seek help from somebody with a PhD in Cryptanalysis.

[monarch_dodra]

Assuming you are using a function which works like rand, chances are it is running on a "Linear Congruential Generator". This is the simple algorithm which is used by most implementations of rand.

They are very simple, and very efficient when all you need is uniform randomness. However, they have some correlation problems (under some circumstances, they are not pseudo random), and they are crackable in cryptography.

My recommendation is to google "Cracking Linear Congruential Generator". You'll get many good results. Take it from there

On a side note, I find it funny how when people need advanced mathematical/Theoretical numerical analysis/Computer Theory, they come to C++ boards. Guess we're just that skilled

[mary_201091]

Hi, if I have a sequence of 1000 random numbers generated by a linear congruential generator of the form:

Xn+1=Xn*a+c mod 32

And i know that the 1000 numbers are extracted from the bits 30-16 (15 bits) of the numbers generated with the formula above. (i.e, they range from 0 to 32767).

How can i predict the 10 next numbers, i.e, how can i calculate the a, c and seed(Xo) values?

I know that it is possible, but i don't have access to the next paper, which i think could be very useful:

http://portal.acm.org/citation.cfm?id=66886


Thanks a lot for your help

[monarch_dodra]

If your goal is just craking the random number generator, and you have access to the compiled/runnable code, then simply dis-assemble the code:

http://stackoverflow.com/questions/1...280765#1280765

If what you want is the formula to crack any high bit LCG, then I suggest you cough up the dough to read that paper. As I said before, we're C++ coders, not cryptanalysts.

That and your request may be braking some rules about not helping with hacking, so I will stop here.

[mary_201091]

Hi again,

I'm studying Engineering and i have a task consisting of getting the next 10 numbers given the first 1000, and that is my only goal, not hacking.

Thanks

[monarch_dodra]

Hi again,

I'm studying Engineering and i have a task consisting of getting the next 10 numbers given the first 1000, and that is my only goal, not hacking.

Thanks

I wasn't accusing you of anything, I was just saying your question could be ill interpreted.

I have two questions:
1 - What could "studying Engineering" possibly have to do with this task?
2 - If this is an assignment, you'd better clear it up with your professor, as the question is really Phd research level.

[andrey_zh]

A proposal: May be the period of generator is shorter than 1000. Let us number the given sequence from 1 to 1000. Search for 1000-th number among first 999. If found, say it's i-th check whether (i-1) == 999, (i-2) == 998 and so on(1). Tip: search backwards i.e. from 999 to 1. You should find the loop, then determinate its length. This loop is called a period of PRNG.

The period of standard rand() is about 230, as I remember.

I hope this will help you. Good luck!

P.S.
(1) Thats for the case when inner state of generator is "wider" than output. For example, rand_seed = (rand_seed * 25173 + 13849) % 65536 has a period of 65536, but the you "shrink" its output with random() % 200.

[nuzzle]

The period of standard rand() is about 230, as I remember.

Hardly. If rand() would repeat itself after just 230 numbers it would be useless.