Monday, May 02, 2005

heads... heads... heads...

In a study of 32 random number sources, it was found that pi (whose digits have been long thought to have no internal structural relationships) has less entropy than many software pseudorandom number generators (RNGs). This is really only of interest to cryptographers and number theorists... the study does not imply that pi has structure at any scale, just that under certain circumstances it can be outperformed as an RNG by other processes.

Since the digits of pi have been used as a source of randomness for many cryptographic processes, this discovery falls into the realm of "what if?". What if computers were a million times more powerful than they are now? What if all of the worlds resources were committed to breaking a code? Sound absurd? Bletchley Park's work (which still seems almost impossible) during World War II wasn't that long ago.

Humans are relatively poor at producing randomness, and only slightly better at identifying it. We (and as a result, our creations) tend to see structure where there isn't any, or to miss structure that is actually present. On a long enough time scale, for example, when I've set Winamp to randomly shuffle through a playlist, I shouldn't be all that surprised if it played the same song three times in a row. But subjectively this wouldn't seem 'random', despite the fact that if the process was truly random each song (including the last song played) has an equal chance of being selected to play next.

A coin flipped a few million times would, somewhere in there, have a run of 25 'heads' in a row. In the digits of a truly random process, any possible sequence of numbers will appear at least once... your credit card number, my birthdate, 1234567890, anything. From a cryptographic standpoint, problems arise if such a string of numbers is repeated, especially if that repitition belies some underlying structure.