June 12, 2001

Connoisseurs of Chaos Offer a Valuable Product: Randomness

By GEORGE JOHNSON

In 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.

Perverse as all this may sound, the connoisseurs of chaos are offering a valuable commodity. For cryptography, game-playing, sociological surveys and various scientific calculations, people often need series of numbers that are devoid of pattern. And that is a tall order. Generating true randomness is one of computer science's most difficult challenges.

"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.

Or they might need to perform a scientific experiment. A sociologist or a statistician surveying a random sample of the public, a biologist analyzing the mercurial spread of a disease or the growth of a population, a psychologist studying whether an avowed clairvoyant can guess the identities of hidden cards with a success rate better than chance — all need random numbers to calculate the uncertain outcomes of pro- cesses that can only be described using probability.

"The world consists of the tension between order and chaos," said Gregory Chaitin, a mathematician at the I.B.M. Thomas J. Watson Research Center in Yorktown Heights, N.Y. "When simulating physical phenomena, order is supplied by the laws of physics and chaos is supplied by random numbers."

Before high-speed 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.

RAND's herculean task took years. After the wheel had spun off the numbers, at the rate of one per second, they had to be sifted to expel some maddening regularities and then stored on 20,000 I.B.M. punch cards (50 numbers per card). But further scrutiny showed that some order still lingered. Certain digits tended to appear more often than others. And so the numbers were further scrambled (using a process called modular arithmetic) and then printed out using a machine called a Cardatype.

"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."

But as science's demand for random numbers continued to grow, even the longest tables were quickly exhausted. A way was needed to produce torrents of random numbers on the fly, and nothing could spit out digits faster than a digital computer.

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.

Often this 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 all around.

To build his Hotbits generator, John Walker, who founded the software company Autodesk, decided to go straight to nature's ultimate source, harnessing the quantum randomness that roils beneath the surface of the seemingly hard-edged world.

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.

At Random.org, Mads Haahr, a Ph.D. student in computer science at Trinity College in Dublin, has been using radio static to generate random numbers since 1998 — "23,383,506,944 random bits served so far!" the site recently boasted, a tally updated by the hour. Clients include a Danish television station that runs a computerized backgammon game on the Internet, an Australian radio station that holds drawings to award prizes, and a University of Florida anthropologist who picks random samplings of informants for surveys.

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.

Hotbits and Random.org exist mostly as educational diversions. They don't pour out random numbers fast enough for such voracious demands as ultra high-security cryptography. Several years ago, Mr. Noll and some colleagues at the Silicon Graphics Corporation began an effort to make an industrial strength random-number dispenser out of lava lamps (or, as their maker, Haggerty Enterprises, insists they should be called, "Lava Lite" lamps.)

A lava lamp is a chaotic system, meaning that it is ruled by a phenomenon called "sensitive dependence on initial conditions." The slightest variations in the temperature, the distribution of the "lava," and many other variables lead to wildly divergent patterns in the slow, burbling ballet.

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.

This stream of ones and zeroes still contained an undesirable amount of predictability. The lava, after all, had to stay within the confines of the six stationery lamps — it couldn't go jumping from one to another. A red lava lamp couldn't randomly turn yellow or blue.

To weed out the pockets of order, the scientists sent the signal through an automatic number mangler called a hash function — a kind of distiller of randomness. A tiny fluctuation in the algorithm's input — a subtle variation in the brightness or hue of a single pixel — would cause the output to wildly fluctuate. The result was a smaller, messier bit string — call it Essence of Chaos. Finally these digits were used to seed a heavy-duty pseudorandom generator called a Blum Blum Shub (after its inventors, the computer scientists Lenore Blum, Manuel Blum and Mike Shub.)

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."


Copyright 2001 The New York Times Company | Privacy Information