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
Printable View
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
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 ?
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.
Yes, i would like to know the next 10 numbers of the sequence, if i only know the first 1000.
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.
[ Moved thread ]
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.Quote:
Originally Posted by Lindley
Well, you need to know the seed value that was used. Then you need to run it 1010 times and take the last 10.Quote:
Originally Posted by mary_201091
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.
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 :D
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
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.
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.Quote:
Originally Posted by mary_201091
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.
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.
Hardly. If rand() would repeat itself after just 230 numbers it would be useless.Quote:
Originally Posted by andrey_zh
From Borland C++ 3.1 Help, article rand():
It used to be so in some old C standard (C89 I guess), then it was fixed.Quote:
rand uses a multiplicative congruential random number generator with period
232 to return successive pseudo-random numbers in the range 0 to RAND_MAX.
I think you're loosing some formatting there. I could believe a period of 2^32, not 232.....
This was copied exactly as it is in Borland C++ Help, I believe it was lost before:
Have a look:
(1) http://poli.cs.vsb.cz/c/help/stdlib0.htm#LBL66
(2) http://books.google.lv/books?id=_T-s...%20%22&f=false
Well, it's wrong. The period is 2^32 according to several other sources, and frankly that makes much more sense.
Just tested it on original Borland C++ 3.1. You're right, the period is longer than 232.
I'm surprised, this typo could survive through years and some printed books.
It was probably 2³², but the formatting got lost and got transformed into 232.Quote:
Originally Posted by andrey_zh
As far as I know though, from a standards point of view, rand is entirely implementation dependent.
The only requirements are a seed, and for the output to be a linear distribution between 0 and RAND_MAX, RAND_MAX being implementation defined. Anything else is just speculation on the implementation. For all you know, RAND_MAX could be 32, and the implemention could be Mersenne, with a 2^19937 period.
...
On a side note, I wanted to add that in a PRNG using LCG the values in a "cycle" are completely independent of the seed. The seed only defines the starting point in the cycle.
Hi again and sorry for being so insistent, but i am very interested in solving this task :
I know that the 1000 numbers have been generated using a function like the rand() of Visual C:
Xn+1=(a*Xn+c) mod 2^32
And after doing this, the numbers that we have access to are formed by extracting the bits 30-16 (length:15 bits- numbers range from 0 to 32767).
There has to be a way to calculate the 'a' and 'c' variables having the first 1000 numbers. I insist: i think that the paper "Inferring sequences produced by a linear congruential generator missing low-order bits" contains the algorithm to do that, but i don't have access to it. So, please, i need urgent help.
Thanks a lot!
Go ask on a math forum. They're more likely to be able to help, since you're looking for an equation to solve before you can even think about writing code.
Or just buy the paper.
Seriously, just because the people here code, doesn't mean they hold advanced degrees in mathematics. You're asking your questions in the wrong place. Your problem may be related to programming, but your actual questions are purely mathematical.Quote:
Originally Posted by mary_201091
And just because you code doesn't mean you're mathematically challenged. To be a good programmer you should know some concrete math and this is well within the city limits.Quote:
Originally Posted by Chris_F
Understanding how to look up the relevant paper and implement it is a reasonable expectation. Even understanding the problem statement in mathematical terms.
Actually working out the solution, however, moves into the realm of research; and thus while many of us no doubt could do it given time, that isn't something we're likely to be spending large amounts of time on for someone else's benefit.
Or so you say, but I have yet to see your proof. ;)Quote:
Originally Posted by nuzzle
Proof of what?Quote:
Originally Posted by Chris_F
After the last post of the OP I think I know how to solve this problem but that's not important.
What's important is the discussion itself and who are you trying to curb it?
...... you use the LLL algorithm
I meant proof as in mathematical proof.Quote:
Originally Posted by nuzzle
What does that have to do with anything. This isn't a math forum.Quote:
Originally Posted by Chris_F
It wasn't my intention to offend you. The sarcasm is unnecessary.Quote:
Originally Posted by nuzzle