What are the most effective algorithms to find random number?

Question

I was reading the Ramsey's Theory stating "complete disorder is impossible". Is there any algorithm to generate random numbers for a long period of time without there being any relation from one set of random numbers to any other set?

Answer 1

As other answers mentioned, any deterministic process (such as Turing/Register Machines) can not produce 'philosophical' or 'true' random numbers. Allow me to answer a slightly rephrased question: "What are the most effective algorithms for finding pseudorandom numbers?"

There are arguably four important properties to consider in pseudorandom number algorithms:

• Security/Hardness of prediction (under varying contexts, i.e. given different amounts of information about the internal state of the algorithm as it runs or bits generated from its output)
• Cycle length, the amount of time it takes for the algorithm to enter into a cycle / repeat its output (and also how this cycle length is distributed according to its input; whether there are some inputs that cause very short cycles)
• Distribution of output values (usually this distribution can be 'flattened' into the uniform distribution using various tricks, but this introduces additional overhead)
• Speed of the algorithm

There is an old engineering joke involving steam engines. An engineer that specialized in trains confronts his investor, telling him that steam engines have three properties: speed, safety, and cheapness; and that due to some fundamental laws of physics, steam engines can only be designed with two of the three properties.

This story relates well to the current state of pseudorandom number generators. Many algorithms are believed to have several of these properties, but no algorithm (as far as I know) is known to have all of these properties.

And so you must choose the algorithm most appropriate for your application. For example, in Computer Graphics algorithms often use Monte Carlo techniques to find an approximate solution to raytracing problems. Obviously for these applications a long cycle of non-redundant, uniformally distributed outputs are required. The faster this algorithm works, the better. Because the application does not need to keep its bits safe from an adversarial entity, rendering algorithms are free to use non-secure PRGNs that simply pass statistical randomness tests. Monte Carlo applications like this are popular and can be encounterd in statistical physics, primality testing (another) and other probabilistic algorithms, Computer Go, and many more places.

For these types of applications, Lagged Fibonacci Generators have been popular. The Mersenne Twister has in recent years been adopted more and more frequently (despite some criticism). The Mersenne Twister is generally easy to predict and should not be used for applications where hardness is a requirement (caveat: some research has been done in developing variants that are thought to be secure in this manner).

There are some applications that need security garuntees. For example, in Interactive Proof Systems, verifiers need to challenge provers with random decisions. If the prover is capable of predicting the verifier's decisions, the protocol breaks down and we get can get no garuntees on the validity of the proof. For this application, a low speed on the algorithm is an acceptable loss for a hardness garuntee (the prover does almost all of the processing in these schemes). Similarly, when choosing bits of prime numbers to generate an RSA key, it is acceptable to absorb the one-time cost of a slow algorithm that has some garuntee of unpredictability.

There are a number of cryptographically secure pseudorandom number generators. However, the level of security varies greatly between these algorithms. One can use symmetric encryption algorithms and hash functions as PRNGs, although this is generally not suggested in the literature. Fortuna and Yarrow (both by Bruce Schneier) are considered cryptographically secure. However, these are examples of algorithms whose security proofs are derived from the statement "all known methods for breaking PRNGs fail on this algorithm" which is considered a weaker security proof than that of explicitly showing an intractibility proof from reasonable complexity assumptions. Blum Blum Shub is an algorithm noted for its unusually strong security proof.

Answer 2

No, not recursively.

The idea that randomness is absence of predictable pattern is usually formalised by Martin-Löf randomness (see WP, Algorithmically random sequence). Martin-Löf randomness consitutes a recursive degree (as a mass problem) stronger than the base recursive degree, so it cannot be generated by a machine. See Simpson, 2005, Mass problems and randomness.

Answer 3

If you want a true random number generation, you need to get the randomness from some physical process, like thermal noise. These sources are usually biased; you can use an extractor to transform a weak source of randomness into a uniform distribution. In practice, one can use a cryptographic hash such as SHA, although its security as an extractor doesn't seem to be proven yet.

Answer 4

In practical terms the way to generate "random" numbers in a computer is totally deterministic. The most commonly used method is explained here http://en.wikipedia.org/wiki/Linear_congruential_generator