Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given a start of a sequence of random numbers generated by some random number generator (of which we don't have the implementation), can we predict the next numbers in the sequence?
For example, having a series of random numbers like this
40 46 15 37 9 4
32 26 5 33 17 21
12 19 13 36 25 29
These are the output numbers from a random number generator and I want to know the pattern that was used to generate them.
It is a well-known fact concerning (cryptographically secure) pseudorandom generators (PRGs) that pseudorandomness is equivalent to next-bit unpredictability. That is, distinguishing the output of a PRG from the uniform distribution is just as hard as predicting its next bit of output (when the PRG works on a uniformly distributed seed). This goes back to a result by Yao.
Further reading:
If we are talking about standard (i.e., not necessarily cryptographically secure) random number generators (RNGs), then things are a bit different. If the RNG simply has to fulfill a set of heuristics, then it can be the case that it does so despite being (almost) fully predictable. (As an extreme example, consider the rather naive heuristic $\lim_{n \to \infty} E(|G(1^n)|_0) = \lim_{n \to \infty} E(|G(1^n)|_1) = \frac{1}{2}$, that is, the string $G(1^n)$ tends to have just as many zeroes as ones and the "generator" $G(1^n) = 0^{\lfloor \frac{n}{2} \rfloor} 1^{\lceil \frac{n}{2} \rceil}$.)
Breaking such an RNG would involve statistical tests and ad hoc methods; your chances of success depend on what the heuristics are and how much computational power and RNG data you have available. Without having detailed these things, it cannot really be said whether it is feasible to break it or not.
It depends on the random number generator.
If you use random numbers for physical simulations, or maybe in a computer game, you don’t care whether the random numbers are predictable or not. What you care about is that you can produce different sequences, and often that you can replay a sequence. And you like one that is fast.
In cryptography, or if you run a lottery, you want numbers that are not predictable. Some random number generators have that property, some don’t. Those that cannot be predicted are called “cryptographic”.
Your average linear congruential random number generator is predictable, but it can be hard work. If I use one with 32 bit state, and give you the results of 50 simulated coin throws, and you know how I calculated the outcome, you can write a program easily that identifies the seed and predicts the next coin throws in a few minutes. If you don’t know my exact code, it is a lot harder. If I used a cryptographic RNG it would be impossible.
