How do computers generate random numbers?

How do computers generate random numbers?

This may have been asked before, but I couldn’t find it. :rolleyes:

Thanks

Truly random numbers? No. There is no determininistic algorithm that can generate true random numbers. Computers use any of several algorithms for generating pseudorandom numbers, which are good enough for most purposes.

Peripheral devices have* been developed by researchers using truyly random natural events, such as nuclear decay and semiconductor thermal noise, to generate true random numbers that can be fed to a computer through an interface. But no computer on its own can do so.

Here is some more information on pseudorandom number generation.

Random number generation is a complex topic. Your best bet is to start with these previous threads:

http://boards.straightdope.com/sdmb/showthread.php?s=&threadid=90874

http://boards.straightdope.com/sdmb/showthread.php?s=&threadid=42913

The new Via Cyrix III (Nehemia, I believe) has become the first mainstream CPU to contain a true random number generator. IIRC, it generates random numbers based on RF interference picked up from a tiny antenna contained on the CPU. Via claims that this provides a revolution in security, though realistically any application where real random numbers were required probably wouldn’t be running on such a slow CPU:)

NOTHING is RANDOM!

Cite? Quantum mechanics says otherwise. And before you say it, yes, so does superstring theory and M-theory.

The random number function in BASIC for the Commodore 64 home computer got it’s “random” numbers by accessing the computer’s internal clock and somehow generating a random number from what it found there. It wasn’t a “true” random number in the sense that is being spoken of in earlier posts, but hey, if all you wanted to do was write a program to generate lotto numbers at random, or to generate random numbers to control the locations of items at the start of an adventure game, etc., etc., it did the trick just fine.

Just a couple of nitpicks, Q.E.D:

  1. There are, unfortunately, a bunch of different definitions of “random”. QM randomness is essentially the strictest - the decay of a single isolated nucleon should be entirely unpredicatable by any means, as far as we can tell. OTOH, “statistical randomness” essentially means that , for a given set of data, all possible subsets occur equally frequently. This can be met by some things that aren’t “really” random, like the sequence of digits in pi, which are easily predictable. In between, there’s a standard for “cryptographically strong” randomness. This essentially means “not mechanistically produced, and not mechanistically predictable” (I’m simplifying here, as with all these definitions). “Pseudorandom” numbers are mechanistically produced, but appear unrelated if you don’t look behind the curtain.

  2. If you’re wondering why I brought that up, it’s to clarify your statement that

It is true that any deterministic algorithm can only produce pseudorandom numbers. It is not true that special entropic devices are required to generate cryptographically strong randomness, because a few of these are already attached to most computers - namely the mouse, keyboard, and other human-input devices. If you treat these inputs correctly (get the time between events, file off the most significant digits, and run the remainder through a smoothing algorithm that doesn’t lose randomness), you’ve got a cryptographically strong RNG right there. Linux (and nowadays, some other Unices) does this automatically through the kernel, so any program has access to an entropy pool of they need it. Some other OSes have what’s known as an “entropy gathering daemon” that does the same thing.

Of course, if you’re running a server, or a research cluster, there’s probably not going to be enough human input available fast enough to supply this. Even with human input, you might well want more entropy available. That’s what the fancy gadgets are good for.

Some Guy just stole my thunder.
Another good example of this is PGP on Mac or Windows. When you generate a key pair it will tell you to move the mouse. It then takes the x/y input of your mouse movements to add to the random seed it uses

So can someone answer the revised question, “How do computers generate psudorandom numbers?” Does my scientific calculator use the same process?

The computer generates a sequence of integers:

I[sub]j+1[/sub] = (aI[sub]j[/sub] + c) mod m,

and usually returns the real number between 0 and 1:

I[sub]j+1[/sub]/m.

Choice of a, c and m is important.

I’ll give an example.

We’ll take:

a = 106
c = 1283
m = 6075.

Let I[sub]1[/sub] = 1 (this is called the “seed”).

I[sub]2[/sub] = (106 x 1 + 1283) mod 6075
= 1389 mod 6075
= 1389
1389 / 6075 = 0.22864

I[sub]3[/sub] = (106 x 1389 + 1283) mod 6075
= 148517 mod 6075
= 2717
2717 / 6075 = 0.44724

I[sub]4[/sub] = (106 x 2717 + 1283) mod 6075
= 289285 mod 6075
= 3760
3760 / 6075 = 0.61893

I[sub]5[/sub] = (106 x 3760 + 1283) mod 6075
= 398560 mod 6075
= 3685
3685 / 6075 = 0.60658

fyrefiend’s brain tries to climb out of his left ear
I really hate math…

Ahhhh. I think you’re too clever for the likes of us Desmostylus.

:smiley:

I generate random numbers all the time! Here, lemme pick the first number that comes to mind…

Hmmm…

See?!? Random!

aeropl wrote

Not sure if you’re asking for a mathematical equation or a process.

I’ll give you a high level of the typical process.

In general, you collect a bunch of numbers that have some level of randomness in them (more about this below), and mesh them together (more about this as well). To generate your next psudorandom number, you again collect some more numbers, and this time, in addition to meshing these numbers together, you also mesh in the previous psudorandom number.

A couple of key concepts in this process:

Entropy
If you pick some number as a source of randomness, it will contain some level of randomness, but it may not be (and usually will not be) completely random. For example, if you grabbed the current date and time, to a precision of a microsecond, you’d find that it will be very hard for someone to guess what microsecond was chosen, but very easy to guess what year was chosen. This concept is called entropy. In one such chosen number, you’ll have some level of entropy, and the more sources of entropy you can accumulate, the higher the level of entropy will be for your final number. Sources of entropy include current time, time since last user input, number of packets received in last second, etc. There are tons of places you can grab psudorandom numbers in a computer. You can search on “entropy” or “information theory” to learn more. A particularly excellent book is “Applied Cryptography” by Bruce Schneier. It has a scary name and is fairly large, but it’s surprisingly readable and enjoyable.

Cryptographic Hashing
There exists a type of mathematical process called hashing. Hashes are by definition one way. Say you take a number X and hash it to form Y. A hash is such that it’s easy to generate Y given X, but it’s very difficult to get X given Y. Hashing is the process that’s used to do the “meshing” I referred to above. MD5 and SHA are popular hashes.

Random numbers are particularly important for various security algorithms. Though the point is true that purely random numbers are impossible without special hardware, you can come close enough for pretty much all practical purposes. Also, hardware to deliver real randomness is pretty inexpensive if you really need it.

I think we need to define the problem better. Generating one random number is not difficult at all (ask Spoofe). The problem is generating series of random numbers and this is what needs to be defined. The problem is that a strictly mathematical generator will output always the same series when given the same seed (which may be desirable or undesirable). If you want a totally “random” number you need a new random seed and start over again. Which really doesn’t resolve the problem becuse you “need a random number to get a random number”. So, as has been said, there are many different ways of approaching this. External devices (clock, mouse, noise generator, etc) can be used for this.

Not quantum mechanics, but the Copenhagen interpretation of quantum mechanics. Other interpretations can be totally deterministic.

Here is a discussion of Krueger numbers which mentions the infamous RANDU random number generator (in the sense of Demostylus), which wasn’t a random number generator.

The pathological case given in Sedgewick is:

a = 19
c = 1
m = 381.

Let I[sub]1[/sub] = 0

I[sub]2[/sub] = (19 x 0 + 1) mod 381
= 1 mod 381
= 1
1 / 381 = 0.002625

I[sub]3[/sub] = (19 x 1 + 1) mod 381
= 20 mod 381
= 20
20 / 381 = 0.05249

I[sub]4[/sub] = (19 x 20 + 1) mod 381
= 381 mod 381
= 0
0 / 381 = 0.00000

I[sub]5[/sub] = (19 x 0 + 1) mod 381
= 1 mod 381
= 1
1 / 381 = 0.002625

This case cycles through (0, 1, 20) over and over. Which, of course, doesn’t work well as a rondom number generator.