<p>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?"</p>

<p>There are arguably four important properties to consider in pseudorandom number algorithms:</p>

<ul>
<li>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)</li>
<li>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)</li>
<li>Distribution of output values (usually this distribution can be 'flattened' into the uniform distribution using various tricks, but this introduces additional overhead)</li>
<li>Speed of the algorithm</li>
</ul>

<p>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.</p>

<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Monte_Carlo_method_in_statistical_physics">statistical physics</a>, <a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">primality testing</a> (<a href="http://en.wikipedia.org/wiki/Solovay%E2%80%93Strassen_primality_test">another</a>) and other <a href="http://en.wikipedia.org/wiki/Randomized_algorithm">probabilistic algorithms</a>, <a href="http://en.wikipedia.org/wiki/Computer_Go">Computer Go</a>, and <a href="http://en.wikipedia.org/wiki/Monte_Carlo_method">many more places</a>.</p>

<p>For these types of applications, <a href="http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator">Lagged Fibonacci Generators</a> have been popular. The <a href="http://en.wikipedia.org/wiki/Mersenne_twister">Mersenne Twister</a> has in recent years been adopted more and more frequently (despite some <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf">criticism</a>). 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).</p>

<p>There are some applications that need security garuntees. For example, in <a href="http://en.wikipedia.org/wiki/Interactive_proof_system">Interactive Proof Systems</a>, 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.</p>

<p>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. <a href="http://en.wikipedia.org/wiki/Fortuna_%28PRNG%29">Fortuna</a> and <a href="http://en.wikipedia.org/wiki/Yarrow_algorithm">Yarrow</a> (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. <a href="http://en.wikipedia.org/wiki/Blum_Blum_Shub">Blum Blum Shub</a> is an algorithm noted for its unusually strong security proof.</p>

CC BY-SA 2.5
2010-08-24T21:20:28.267Z
2010-08-24T22:21:01.703Z
2010-08-24T22:21:01.703Z
Ross Snider
<p>No, not recursively.  </p>

<p>The idea that randomness is absence of predictable pattern is usually formalised by Martin-Löf randomness (see WP, <a href="http://en.wikipedia.org/wiki/Algorithmically_random_sequence" rel="nofollow">Algorithmically random sequence</a>).  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, <a href="http://www.math.psu.edu/simpson/papers/massrand.pdf" rel="nofollow">Mass problems and randomness</a>.</p>

CC BY-SA 2.5
2010-08-24T12:26:40.640Z
2010-08-24T12:26:40.640Z
Charles Stewart
<p>If you want a <em>true</em> 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 <a href="http://en.wikipedia.org/wiki/Randomness_extractor" rel="nofollow">extractor</a> 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 <a href="http://eprint.iacr.org/2009/136.pdf" rel="nofollow">doesn't seem to be proven yet</a>.</p>

CC BY-SA 2.5
2010-08-24T18:29:04.757Z
Wow, thermal noise sounds good! Never really thought of that.
tsudot
CC BY-SA 2.5
2010-09-01T17:42:44.990Z
Radioactive decay has a true stochastic behavior and can be used as a source of randomness.
Randall Schulz
CC BY-SA 2.5
2010-09-01T21:13:27.490Z
Back in the days :http://www.lavarnd.org/index.html
Sylvain Peyronnet
CC BY-SA 2.5
2010-08-24T17:47:35.137Z
2010-08-24T19:33:09.467Z
2010-08-24T19:33:09.467Z
Felipe Lacerda
<p>In practical terms the way to generate "random" numbers in a computer is totally deterministic. The most commonly used method is explained here <a href="http://en.wikipedia.org/wiki/Linear_congruential_generator" rel="nofollow">http://en.wikipedia.org/wiki/Linear_congruential_generator</a> </p>

CC BY-SA 2.5
2010-08-25T21:51:21.657Z
If they come from a deterministic algorithm, they aren't random numbers.  By definition.
Jeffε
CC BY-SA 2.5
2010-09-01T20:46:40.803Z
@JeffE Which makes them, also by definition, *pseudorandom* numbers.
Yaser Sulaiman
CC BY-SA 2.5
2010-08-24T08:41:00.207Z
2010-09-01T17:10:12.957Z
2010-09-01T17:10:12.957Z
carlosdc
<p>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?</p>

CC BY-SA 2.5
2010-08-24T19:54:20.470Z
Could you clarify your question please?  What do you mean by "any relation" -- do you mean uncorrelated, orbits being disjoint, or something else?  What do you mean by "a long period of time" -- are you looking for a RNG with a long period, or one that is aperiodic?
András Salamon
CC BY-SA 2.5
2010-08-26T17:24:56.633Z
"...without there being any relation..." is just too vague. Voting to close as "Not a real question".
Aryabhata
CC BY-SA 2.5
2010-09-01T17:47:56.807Z
I don't quite see the relevance of Ramsey's Theorem.
Emil
CC BY-SA 2.5
2010-09-04T10:09:32.120Z
@Andras What I meant was, that suppose we take a subset, m of random numbers generated and another subset, n from the same list of random numbers. Then these two lists shouldn't have any function f, such that m can map to n. f(m) != n.

I hope I'm a bit clear now.
tsudot
<ds.algorithms><randomness>
What are the most effective algorithms to find random number?
tsudot
# What are the most effective algorithms to find random number?

(Asked by: username_0 on 2010-08-24)

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?

**Tags:** ds.algorithms, randomness
> **Comments:**
> **username_1**: Could you clarify your question please?  What do you mean by "any relation" -- do you mean uncorrelated, orbits being disjoint, or something else?  What do you mean by "a long period of time" -- are you looking for a RNG with a long period, or one that is aperiodic?  
> **username_2**: "...without there being any relation..." is just too vague. Voting to close as "Not a real question".  
> **username_3**: I don't quite see the relevance of Ramsey's Theorem.  
> **username_0**: @Andras What I meant was, that suppose we take a subset, m of random numbers generated and another subset, n from the same list of random numbers. Then these two lists shouldn't have any function f, such that m can map to n. f(m) != n.  I hope I'm a bit clear now.  

---

## 4 answers

### Answer by username_4 on 2010-08-24. Score: 8

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](http://en.wikipedia.org/wiki/Monte_Carlo_method_in_statistical_physics), [primality testing](http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) ([another](http://en.wikipedia.org/wiki/Solovay%E2%80%93Strassen_primality_test)) and other [probabilistic algorithms](http://en.wikipedia.org/wiki/Randomized_algorithm), [Computer Go](http://en.wikipedia.org/wiki/Computer_Go), and [many more places](http://en.wikipedia.org/wiki/Monte_Carlo_method).

For these types of applications, [Lagged Fibonacci Generators](http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator) have been popular. The [Mersenne Twister](http://en.wikipedia.org/wiki/Mersenne_twister) has in recent years been adopted more and more frequently (despite some [criticism](http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf)). 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](http://en.wikipedia.org/wiki/Interactive_proof_system), 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](http://en.wikipedia.org/wiki/Fortuna_%28PRNG%29) and [Yarrow](http://en.wikipedia.org/wiki/Yarrow_algorithm) (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](http://en.wikipedia.org/wiki/Blum_Blum_Shub) is an algorithm noted for its unusually strong security proof.


---

### Answer by username_5 on 2010-08-24. Score: 6

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](http://en.wikipedia.org/wiki/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](http://www.math.psu.edu/simpson/papers/massrand.pdf).


---

### Answer by username_6 on 2010-08-24. Score: 4

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](http://en.wikipedia.org/wiki/Randomness_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](http://eprint.iacr.org/2009/136.pdf).

> **Comments:**
> **username_0**: Wow, thermal noise sounds good! Never really thought of that.  
> **username_7**: Radioactive decay has a true stochastic behavior and can be used as a source of randomness.  
> **username_8**: Back in the days :http://www.lavarnd.org/index.html  

---

### Answer by username_9 on 2010-08-24. Score: 3

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>

> **Comments:**
> **username_10**: If they come from a deterministic algorithm, they aren't random numbers.  By definition.  
> **username_11**: @JeffE Which makes them, also by definition, *pseudorandom* numbers.  

---

