Google Answers Logo
View Question
 
Q: pseudo-random numbers ( Answered,   4 Comments )
Question  
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.
Answer  
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.
Comments  
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

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

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 Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy