﻿ Petzold Book Blog - Computers, Randomness, and Alan Turing

PETZOLD BOOK BLOG

#### Charles Petzold on writing books, reading books, and exercising the internal UTM

 Recent Entries < Previous Browse the Archives Next > Subscribe to the RSS Feed

## Computers, Randomness, and Alan Turing

December 6, 2007
Roscoe, N.Y.

“Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.” — John von Neumann, 19491

Jeff Atwood's recent and earlier blog entries remind us of one numerical job that computers really stink at: generating random numbers.

I suspect that Alan Turing was one of the first people to realize this. His famous 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" begins by discussing how to specify the actions of computing machines to calculate real numbers. He quickly determines that the numbers computable by all such machines — which he classifies as the "computable numbers" — are merely an enumerable subset of the real numbers. This is easily provable, but also understandable when one considers that the vast majority of real numbers are simply strings of truly random digits, so how are you going to get a completely deterministic machine to compute them?

For example, if you tried to compute the digits of a number using a typical pseudo-random number generator such as the rand function in C or the System.Random class in the .NET Framework, you'd eventually reach the end of the cycle and start repeating digits, at which point you're merely calculating a rational number.

Skip ahead 12 years. Alan Turing is a Reader in the Department of Mathematics at Manchester University under M.H.A. ("Max") Newman, the former Cambridge mathematician whose class in the Foundations of Mathematics Turing had attended in 1935, and who guided Turing's classic paper to publication. Both Newman and Turing are heavily involved in one of Manchester University's seminal computer projects, the Ferranti Mark I developed between 1949 and 1951. (Several years later Max Newman wrote Turing's obituary for the Royal Society and outlived Turing by 30 years.)

At the request of Turing an instruction to generate a random number from a noise source was provided. Unfortunately, the numbers turned out to be not particularly random, and debugging was difficult because programmes were not repeatable; consequently the instruction fell into disuse.2

Wouldn't it have been interesting for Steve Wozniak or Don Estridge to have also decided that every computer needed a hardware random number generator, and for that feature to have become a standard part of the machines we use today?

1John von Neumann, Collected Works, Volume V, Design of Computer, Theory of Automata, and Numerical Analysis (Macmillan, 1963), 768. The statement was originally made at a symposium on Monte Carlo methods in 1949.

2Martin Campbell-Kelly, “Programming the Mark I: Early Programming Activity at the University of Manchester,” Annals of the History of Computing, Vol. 2, No. 2 (April, 1980), 136.

 Coming May 19, 2008!Available for Pre-Ordering Wiley Amazon US Amazon Canada Amazon UK Amazon Deutsch Amazon Français Amazon Japan Blackwell

I believe there is now a hardware random function somewhere in the system. Intel added one to the Firmware Hub (BIOS) chip in the 820 chipset and others of the same generation (http://developer.intel.com/design/chipsets/manuals/29802901.pdf). I don't know whether this was ever implemented by other manufacturers, though. The Trusted Platform Module commonly fitted on new systems (especially laptops) also contains a hardware random number generator.

Windows Vista allows the TPM to be accessed directly with the TPM Base Services API. I don't know whether the cryptographic (supposedly more secure with greater sources of entropy although still predictable) RNG API(s) (CryptGenRandom, BCryptGenRandom for 'Next Generation Cryptography API' in Windows Vista, Server 2008) use the hardware RNG at all, if available. It has recently been suggested that CryptGenRandom is predictable if you have access to the process that is running it because certain of the inputs to the algorithm are in user-mode memory and the algorithm itself runs in user mode (http://cve.mitre.org/cgi-bin/cvename.cgi?name=2007-6043).

I don't know how good these hardware random number generators are. Intel suggest running the 82802 Firmware Hub's output through the FIPS 140-1 test (http://csrc.nist.gov/publications/fips/fips1401.htm#sec4.11.1) before using it as a true random source, although this is more to check that you're actually talking to an implementation of the RNG rather than some other piece of hardware.

Mike Dimmick, Thu, 6 Dec 2007 21:42:51 -0500 (EST)

Wow! Thanks for the information. — Charles

The TPM (Trusted Platform Module) has a hardware RNG.

The TPM is currently installed on IBM laptops.

allan foster, Fri, 13 Mar 2009 13:48:36 -0400 (EDT)

 Recent Entries < Previous Browse the Archives Next > Subscribe to the RSS Feed