|
|
Subject:
pseudo-random numbers
Category: Computers > Algorithms Asked by: x2862-ga List Price: $20.00 |
Posted:
08 Jun 2002 06:12 PDT
Expires: 15 Jun 2002 06:12 PDT Question ID: 23788 |
I have been using some programs that generate random numbers. i wanted to know if there is a way to get the next numbers in the pseudo-random sequence if the algorithm and seed are not known.and is there a program that can take the numbers allready generated and guess the next ones. |
|
Subject:
Re: pseudo-random numbers
Answered By: davidsar-ga on 08 Jun 2002 07:21 PDT |
This is one of those "a million monkeys at a million typewriters for a million years" type of questions. In theory, they might produce a copy of Hamlet. In practice, it'll never happen. Any decent pseudorandom number generator should have enough of a resemblence to true randomness as to make the type of prediction of you're asking about next to impossible. As noted on: http://webnz.com/robert/true_rng.html 'Pseudo-random number generators...use a formula to generate numbers which behave very like genuine random numbers and are widely used for simulations of random processes and statistical methods. In most cases a good pseudo-random number generator seems to work as you would expect a genuine random generator to work." In other words, predicting the next number in the series shouldn't be an easy task, even for sophisticated software analyses. However, pseudorandom number generators are not perfect, as noted at another site on the topic: http://random.mat.sbg.ac.at/tests/ "Every generator has its regularities which, ocassionally, may become deficiencies. Hence, in a given application, even reliable generators may fail." Here's where the million monkeys come in. If you could generate millions of numbers from your program, and subject them to some of the statistical tests that are freely available, then you might begin to zero on some of your program's irregularities. With enough information, you could probably, eventually, identify the actual algorithm in use (unless its proprietary) and then you'd have predictability from any given seed number. Some literature about tests, with links to the tests themselves, are at http://random.mat.sbg.ac.at/tests/. Bottom line: with millions or billions of numbers, tons of computing power, and lots of time, it might be possible to 'reverse engineer' your random number generator. Professional cryptographers sometimes do this sort of thing, but there's an awful lot of human ingenuity involved in this, not just a simple "plug the numbers into the software" type of thing. From a practical point of view, however, you won't be able to predict the next number (unless your random number generator is so poorly programmed as to be obviously predictable, even to the naked eye). Hope this answers the question to your satisfaction. Let me know if you need additional information. |
|
Subject:
Re: pseudo-random numbers
From: calebu2-ga on 08 Jun 2002 08:51 PDT |
True, it may be very hard to reverse engineer the random number generator, but from my experience with using random number generators (for monte carlo simulations), some of the standard random number generators (like the one in the c compiler I use, and more than likely the RNG in microsoft excel) have relatively short repeat cycles (how long it takes before you see the same pattern again). I believe that the standard C random number generator repeats after at most 2^32 combinations (which is a pretty decent sized number - 4 billion, roughly) - it could be as small as 2^16 (65536). In that case, you wouldn't be far wrong if you just got the random number generator to produce all the numbers until it repeats and then search for your string in it. Check out http://sprng.cs.fsu.edu/ - this is the RNG I use instead of the built in one. I know that this isn't exactly a high tech answer (so be constructive with your flames, fellow researchers :), but sometimes stupid brute force approaches can work. |
Subject:
Re: pseudo-random numbers
From: dcrypt-ga on 13 Jun 2002 05:48 PDT |
The answer to your question depends very much on the generator. To the best of my knowledge, the random number generators in most programming languages are generally maximal periodic linear congruency generators. Which means you are really just going something line Xn+1 = (Xn + a) mod b Where Xn is the nth number in the sequence and, a and b are constants chosen so that the sequence is maximal periodic(only repeats after hitting all numbers in 0..b-1) Obvously this is easy to spot and highly predictable. More advanced random number generators(especially crytographic ones), are designed with very non-linear operations, and must produce a gaussian distribution(what you would expect in a real random sequence) and also are non-predicatable both forwards and backwards. If it is one of these then you're probably stuck. It would help if you gave more details on the implementation of the generator? Hope this helps |
Subject:
Re: pseudo-random numbers
From: gunnzi-ga on 18 Jun 2002 06:41 PDT |
Actually the most often used LCG (linear congruental generator) is Xi+1 = Xi * a + b (mod c) This is used in most operating systems. The random numbers repeat and the cycle is at most 2^c and the same number is only outputted once every cycle |
Subject:
Art of Computer Programming, Vol 2
From: ulu-ga on 26 Jul 2002 10:47 PDT |
For detailed information on Random Number Generators, I would suggest: Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition) by Donald Ervin Knuth (Preface) http://www.amazon.com/exec/obidos/ASIN/0201896842 |
If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you. |
Search Google Answers for |
Google Home - Answers FAQ - Terms of Service - Privacy Policy |