How do computers create 'randomness'?

Question

I have just used a function 'rand()' in my algorithm. In fact, it was arc4random() that I used. However, it got me thinking, how is randomness created in a computer system? Can anything ever truly be random when it is produced by a computer?

Answer 1

Randomness is a philosophical concept (though there are several mathematical definitions as well). There are two aspect to randomness generated by a computer, unpredictability and pseudorandomness, which correspond to two different demands from a randomness source:

1. Data produced by the randomness source should be unpredictable, even in principle.
2. Data produced by the randomness source should "behave" as a truly random source.

The approach taken by computers to generate randomness is a combination of both of these flavors. Randomness is generate using a pseudorandom number generator, which is an algorithm designed to churned up numbers which "look random", in the sense that any program employing a randomness source will behave the same regardless of it being given a truly random source or the output of the pseudorandom number generator. ARC4 (usually known as RC4) is such an algorithm, though the first few random bits are known to be somewhat problematic.

A pseudorandom number generator (PRNG) is seeded by initial randomness, known as either a seed or a key. Sometimes we want to fix this initial randomness, for example when debugging a program which uses the PRNG. Other times, it is important that this initial randomness be unpredictable - this is the case in cryptographic applications. It used to be the case that PRNGs are seeded using the exact time-of-day as kept by the computer clock. Nowadays systems are more sophisticated, and harvest random bits from other sources such as keystrokes, CPU, internal devices and network usage, commonly known as an entropy pool. Therefore modern systems are capable of producing unpredictable random numbers.

If it is important to generate truly random numbers (or rather, numbers which are even less predictable), one can resort to hardware number generators, which usually measure thermal noise generated by electric components such as diodes (in the form of voltage or current fluctuations). However even this random output needs to be filtered (through a randomness extractor) to result in a sequence of independent fair coin flips.

Answer 2

Whatever Yuval Filmus said.. In addition to that if you want to learn more about Pseudorandomness, take a look at Sahil Vadhan's awesome monograph on pseudo randomness, available here

Also you can take a look at Marsaglia's KISS99, a nice algorithm (and a C program) that generates 'random' numbers. If you want a short introduction on the this, you can refer to the first chapter of Handbook of Monte Carlo Methods

Also for practical advice on implementing your own random number generator you can refer to this article from David Jones.

(i know you only wanted to know if it was indeed random, Yuval Filmus answered that well enough, but why stop there, go on and learn how they are actually done, the theory and math behind it, I am sure you'll have fun) :)