June 12, 2001
Connoisseurs of Chaos Offer a Valuable Product: Randomness
By GEORGE JOHNSON
n an age when most people seem obsessed with bringing order to their lives — with Day- Timers, Palm Pilots, and even professional anticlutter specialists to wrestle their closets and junk drawers into line — a Web site in Switzerland has been offering a very different service: providing the world with randomness.
Pay a visit to the home page of this purveyor of unpredictability, called Hotbits, and you will hear what sounds like the erratic clicking of a Geiger counter.
It is the sound of neutrons in a radioactive substance spewing out electrons and gamma rays as they decay. This decay is random, as guaranteed by laws of quantum mechanics, so by training a Geiger counter on a sample of krypton 85 and feeding the signal to a computer, Hotbits (www.fourmilab.ch /hotbits) generates a constant stream of random digits. Just fill out an electronic form, saying how many bits you want and they will be dispatched immediately over the Internet.
Or you may turn to one of Hotbits's rivals. Random.org generates
unpredictable sequences of data using a radio tuned between stations,
harvesting the atmospheric noise. Another operation, Lavarand (on the
Web at lavarand.sgi.com), produces random numbers by training digital
cameras on burbling lava lamps.
"Computers are designed to be predictable," said Landon Curt Noll, a mathematician and cryptographer for SystemExperts, a computer security consulting firm. "If they do something we don't expect, we say they are broken."
After expending so much effort to squeeze whimsy and caprice from the circuitry, computer scientists must find ways to trick the electronic clockworks into simulating erratic behavior.
People might need
to generate secret passwords or lottery numbers, scramble sensitive
messages to protect them from eavesdroppers, or mimic the roll of dice
or the dealing of a poker hand.
"The world consists of the tension between order and chaos," said Gregory Chaitin, a mathematician at the I.B.M.
digital computers were invented, mathematicians compiled tables of
random numbers by blindly flipping through phone books, casting dice,
spinning spinners or drawing cards from a hat. As automation came of
age, the RAND Corporation used a kind of electronic roulette wheel to
generate a classic work, published in 1955, called "A Million Random
Digits With 100,000 Normal Deviates." The seemingly oxymoronic term
"normal deviates" (random numbers whose occurrence can be plotted on a
bell-shaped curve) inspired the New York Public Library to shelve the
book in the psychology section.
"Because of the
very nature of the tables," the authors noted in the introduction, "it
did not seem necessary to proofread every page of the final manuscript
in order to catch random errors of the Cardatype."
Therein lay the paradox: how to use order to generate disorder. The best that could be hoped for, it seemed, was pseudorandomness — numbers that, though produced by a completely deterministic and repeatable process, appear to be patternless.
The mathematician John Von Neumann suggested one of the first rather imperfect pseudorandom number generators — a simple procedure, or algorithm, called the middle square method. Arbitrarily pick a number — your cat's birthday, the license plate of the next car that drives by — and use it as a "seed." Square it and take the middle digits. Write down that number and then use it as the seed for the next round. Suppose you start with 357. That number squared is 127,449 and the middle digits are 2,744. Square that and extract the middle digits: 295. Repeat the process again and again: 702, 9280, 1184. So far, so good. But the next number that appears is 18, then 324, then 2, and there is nowhere to go from there.
Mathematicians have come up with far more reliable pseudorandom generators. The digits that come stuttering forth appear to be as patternless as raindrops on pavement or snow on a television set tuned to an empty channel. But even the best algorithms share the same weakness: the numbers are not really unpredictable. If you run the process long enough, the cycle of digits will eventually repeat — a pattern appears. Even worse, anyone with the same seed and algorithm can reproduce the sequence.
doesn't matter, but for applications like cryptography true randomness
can be crucial. An eavesdropper who can guess the seed of the "random"
number used to encode a message can break the cipher. To get a computer
to produce a genuinely unpredictable outcome, it must be opened up to
the outside world — buffeted by a stream of the randomness that courses
Near Zurich he maintains a kind of personal
computer-science exploratorium he calls Fourmilab. (The name means "ant
laboratory" in French, an allusion to Mr. Walker's interest in
artificial life, computer programs that strive to mimic living
creatures.) His Hotbits service receives about 300 requests a day for
its radioactively produced random numbers. Many are used in
parapsychology experiments, conducted in another corner of the
Fourmilab Web site, in which people try to use their mental powers to
alter the outcome of random events.
Faced with a difficult decision, anyone
can go to the site and consult the automated coin-flipping program,
choosing between a Colombian 500-peso piece, an East Caribbean dollar,
a Luxembourgian Euro, or 18 other coins.
Throwing in even more wild cards, Mr. Noll and his cohorts used six
lava lamps, each of a different color. The result was called Lavarand.
Every second a digital camera snapped an image of the fluctuating scene
converting the array of pixels into a string of bits.
The ultimate outcome, the scientists confidently declared, was a truly irreproducible number. In case there was any doubt, they noted that there were yet other sources of unpredictability in the system: Tiny quantum fluctuations from the movement of subatomic particles would affect the behavior of the lava lamps, and the camera itself injected a silent roar of visual static.
In fact Mr. Noll and another Silicon Graphics researcher, Simon Cooper, discovered one day that, pretty as they were, the lava lamps were irrelevant. The system worked even better if they put a cap on the camera lens and simply fed the computer a stream of blind electronic noise. Using this as their source, Mr. Cooper and Mr. Noll are now working on an improved system called LavaRnd. (In the spirit of minimalism the final "a" was dropped from the name, allowing it, Mr. Noll said, to fit on a license plate.)
And so the quality of science's manufactured chaos
continues to improve, bringing its own kind of order. Mr. Haahr, the
keeper of Random .org, said that when he started his enterprise, he was
struck by the irony of deliberately dispensing randomness. "It was a
bit like selling sand in the desert," he said. "But it's not quite like
that because the noise you're getting from Random.org is pure in a way;
it's different from the hustling-bustling cacophony of the information
age. Producing anything that's pure, even noise, takes effort."