Science News Online |
|||||||||
Take a ChanceScientists put randomness to workErica Klarreich Since the dawn of written history, people have exploited the randomness of a roll of a die to inject their games with the thrill of the unpredictable. Today, randomness is finding myriad other uses, such as encrypting credit card numbers in Internet transactions, deciding how to allocate treatments in drug trials, choosing precincts to call in national polls, running online gambling sites, and helping physicists simulate phenomena ranging from the weather to traffic patterns. These applications, however, require many more random numbers than can be obtained from rolling a die. A busy commercial Web site, for example, uses hundreds of thousands of random numbers every minute to mask its users' credit card numbers. And in the research world, computer simulations eat up millions of random numbers in a matter of seconds. To accommodate these needs, researchers are creating a precise science out of something at which toddlers excel: making chaos at breakneck speed. Randomness is a slippery concept, easier to talk about than to define. Scientists instead tend to say what it isn't. A random number is one that can't be predicted. Knowing some of the random numbers in a list doesn't make it easier to figure out the others. Over the past few decades, computer scientists have designed computer algorithms that produce a good approximation of true randomness. These algorithms churn out long sequences of pseudorandom numbers, which are scattered about the number line in roughly the same distribution as random numbers are. These pseudorandom numbers are unpredictable enough for many, but not all, purposes. Now, physicists and computer scientists are figuring out ways to pull true randomness out of the physical world. One Web site, for instance, generates random numbers from the noise of a radio tuned between stations. And a commercial device put on the market last March harnesses nature's ultimate source of randomness: quantum physics, which Albert Einstein famously described as God playing dice. Approximately random Although computers are expert at spewing out numbers, a computer program can't by itself produce random ones. Computers are engineered to behave deterministically, obeying the will of their users. "If a computer does something unpredictable, then we call it broken," says Landon Noll, a cryptographer at the computer security firm SystemExperts in Sudbury, Mass.
However, computer scientists have figured out how to produce computer-generated sequences of numbers that are virtually indistinguishable from random numbers. To get a sense of how these algorithms operate, consider the following highly simplified version of a pseudorandom-number algorithm. First, it's necessary to choose a starting number between 0 and 12, called the seed—say, the number 4. After that initial choice, the algorithm produces each new pseudorandom number by multiplying the preceding number by 17, dividing the result by 13, and taking the remainder.
This particular algorithm is a far cry from randomness, since it quickly falls into a pattern. The first few numbers in the sequence are 3, 12, 10, 1, and then 4, which brings us back to where we started. After that, the sequence simply repeats itself indefinitely. All pseudorandom-number generators eventually fall into a repeating pattern. However, an algorithm that produces an extremely long pattern before repeating can be unpredictable enough to suit many purposes. Mathematicians have constructed effective pseudorandom-number generators similar to the above algorithm by using larger numbers than 17 and 13 and more-complicated procedures for generating the next number in the sequence. One widely used pseudorandom number generator along these lines is the Mersenne Twister, designed in 1997, which produces a sequence of 219,937–1 numbers before repeating. Pseudorandom-number generators are key to computer simulations of complicated physical systems. For example, to search for the characteristic shape into which a protein molecule will fold, researchers start with one possible shape and then make small, random changes in it, checking the stability of each new shape. Whenever the shape has gotten more stable, they replace the old one with the new. Then they repeat the same process, sometimes thousands of times. Similar processes are used to simulate a wide range of phenomena, including weather, traffic flow, stock market swings, and radiation therapy for cancer. A large simulation can swallow up tens of billions of random numbers. As a result, researchers put a high premium on the efficiency of the pseudorandom-number generator they use. The Mersenne Twister, which is one of the fastest pseudorandom-number generators around, is a popular choice. Other pseudorandom-number generators are also widely used, including some that have serious flaws, says David Wagner, a computer scientist at the University of California, Berkeley. For example, many computers come equipped with a random-number generator that alternates between odd and even numbers. A truly random sequence would never have such a regular structure. A faulty random-number generator can wreck a scientific project. In one famous case in 1992, physicists realized that a computer simulation of atomic spins was giving completely wrong answers, even though the pseudorandom-number generator they were using had passed a stringent set of statistical tests (SN: 12/19&26/92, p. 422). Subtle correlations between the numbers the algorithm produced were being amplified by the simulation's calculations and skewing the results. Fortunately, scientists are becoming more aware of the risks of using a pseudorandom number generator, even though they might not understand its workings, says Thomas Lumley, a statistician at the University of Washington in Seattle. "I think most people doing large simulations are educated now," he says. Keeping a secret While the Mersenne Twister does a good job of imitating randomness, mathematicians propose that certain other algorithms, while slower, are closer to true randomness. They are called cryptographically strong algorithms, and their output passes every statistical test that can be performed in a feasible amount of computer time to distinguish random numbers from numbers that fall into a pattern. "If you used a cryptographically strong algorithm to shuffle decks of cards on an online gambling site, then even after I played hundreds of poker hands, I wouldn't be able to predict anything at all about the next hand," says Wagner. These random-number generators are the algorithms of choice for applications such as encrypting credit card numbers in Internet transactions, for which unpredictability is of paramount importance. "Even a hacker who is very smart and is willing to mount a brute-force attack shouldn't be able to predict anything about what random numbers you're generating," Wagner says. Cryptographically strong algorithms, however, share an Achilles' heel with the other pseudorandom number generators. They all require the user to input a starting seed number. If hackers find out the secret seed, they can generate the entire output sequence instantly by using the same algorithm. That's precisely what occurred in 1995, when Wagner, then a graduate student at Berkeley, and his fellow student Ian Goldberg cracked the random-number generator used by the Netscape web browser to secure online transactions. The pair figured out that Netscape was constructing its seeds using easily predicted numbers, such as the time of day. Luckily for Netscape, the two students had no criminal intent. They simply publicized the browser's vulnerability, which Netscape quickly corrected. In recent years, Wagner says, "there have been several other instances of widely deployed systems that have been vulnerable to attack because insufficient attention was paid to generating high-quality randomness." To evade hackers, it's best to choose the seed randomly. However, this creates a chicken-and-egg problem. To generate the random seed using a computer, it's necessary to run a pseudorandom-number generator, which in turn must be started off using a random seed. At some point, there must be a first seed, which a hacker could discover. Harnessing chaos Researchers are now making an end run around this vicious cycle by finding ways to import random numbers from the world outside the computer. These numbers can then be used either as the seeds for computer algorithms or as random numbers in their own right.
Some of the simpler versions extract randomness out of human actions such as the motion of a computer mouse, say, or the time between keystrokes. Others, in a quest for super fast random-number generation, are turning to more-exotic sources of randomness. Most of these exploit chaotic physical systems, for which tiny changes in the starting conditions propagate into dramatic swings in the large-scale behavior of the system. Chaotic systems—such as lottery balls jumping about in a box—are not strictly speaking random, but they generally include elements that are effectively impossible to predict. One of the first of these physical random-number generators, called Random.org, uses a radio to pull random numbers out of the atmospheric noise generated by weather systems. "When we built this in 1997, we bought the cheapest radio we could find," says Mads Haahr, of Trinity College, Dublin, who runs Random.org. "The guy in the shop thought we were crazy because we made him take it out of the box and put in batteries so we could listen to the noise between stations." Haahr's Web site (http://www.random.org/) can generate up to 3,000 random numbers per second. Over the last 6 years, it has dished out more than 61 billion random numbers for free to an eclectic array of users. These include archaeologists choosing which quadrants of a large area to survey; a choreographer selecting the order, timing, and placement of dance steps; online card-playing sites shuffling their virtual decks; the U.S. Environmental Protection Agency determining which companies to include in a random audit of hazardous-material use; and a locksmith deciding how deeply to cut the notches on keys. Another early random-number generator extracted randomness from a very retro source: lava lamps, whose illuminated blobs move unpredictably. In the lavarand project, created by Noll and colleagues in 1996, digital cameras trained on six lava lamps fed images into a computer, which converted the pictures into numbers (SN: 8/9/97, p. 92). The lavarand apparatus is impractical, Noll readily acknowledges. It was intended, he says, mainly as a whimsical proof that it's possible to generate high-quality random numbers from a physical source. While analyzing lavarand's workings, the researchers found to their surprise that most of the noise and unpredictability was coming not from the lava lamps but from the digital cameras. The team's latest version of lava lamp randomness, called LavaRnd, ironically does away with the lava lamps. It's simply a webcam running with its lens cap on. LavaRnd produces 200,000 random numbers per second, more than enough for many cryptography and simulation applications. One of the tricks in designing physical random-number generators such as Random.org or LavaRnd is to erase any bias in the numbers. In a truly random stream of numbers, each combination of digits should appear as often as any other combination. However, in numbers generated from the physical world, this is rarely the case. Even a coin toss, the seeming epitome of randomness, is subtly biased. Earlier this year, mathematicians proved that a tossed coin is slightly more likely to land on the face it started out on than on the opposite face (SN: 2/28/04, p. 131: http://www.sciencenews.org/articles/20040228/fob2.asp). Over the decades, computer scientists have worked out computer algorithms to tackle this problem. In 1951, mathematician John von Neumann came up with a simple algorithm that works on sequences of bits. To balance a sequence between 0s and 1s, von Neumann's algorithm groups the bits into pairs, then discards any pair in which the two bits are the same. If the two bits are different, the algorithm replaces the pair with the first bit—so, for instance, 01 would be shortened to 0. The result is a new sequence that preserves all the unpredictability of the original sequence but in which 0s and 1s appear with roughly the same frequency. Von Neumann's procedure throws away about 75 percent of the original sequence. Computer scientists have more recently come up with less-profligate algorithms, such as one that Noll and his colleagues designed for LavaRnd, called the Digital Blender. "The Blender takes the original structure and chops it up and squeezes it down into a random mash of data," Noll says. Quantum randomness Although chaotic systems are good sources of unpredictability, they are deterministic, at least in principle. Given a precise knowledge of the physical parameters of a given weather system, for instance, it should be possible to figure out exactly what the system is going to do. By contrast, quantum physics—the science of subatomic particles—is intrinsically random. According to its laws, it's impossible to know for sure what a quantum system will do. Researchers are now building random number generators that exploit this unpredictability. One such system called HotBits, created by John Walker of Fourmilab in Switzerland, generates random numbers by timing radioactive decays of Krypton-85 atoms detected by a Geiger counter. These decays happen at random intervals, quantum mechanics dictates. HotBits produces a modest 30 random numbers per second, not enough for the most number-hungry applications. However, another Swiss team has just produced a quantum random-number generator that produces 4 million random bits per second. Unlike Random.org, LavaRnd, and HotBits, this random-number generator is a commercial venture. The new device, a matchbox-size module that can be mounted on a computer's circuit board, is produced by id Quantique in Geneva. It operates by beaming photons of light at a semitransparent mirror. According to quantum theory, each photon has a 50 percent chance of passing through the mirror and the same chance of being reflected, making the device a quantum idealization of a coin toss. The device's creators predict that its simplicity will appeal to potential users. Any machine has the potential to break, and if a physical random-number generator is complicated, it can be hard to tell whether it is in good working order. "You can never definitively test that random-numbers are really random," says Gregoire Ribordy, id Quantique's CEO. "But this generator is so simple that it's easy to test whether it is working properly just by testing the components." Some physicists argue that quantum systems are more purely random than chaotic systems are. Yet in the final analysis, quantum physics and chaos are probably equally good sources of randomness for all practical purposes, Haahr says. To actually predict the behavior of a chaotic system like the weather, for example, "you would probably need knowledge of the position and velocity of every single molecule in the planet's weather systems, which is of course infeasible," he observes. "It's hard enough to predict the weather for the next couple of days." Letters: Wasn't Einstein so irritated at the thought of randomness in the universe that he said, "God does not play dice with the universe"? Your article seemed to suggest that Einstein endorsed quantum physics, which I was under the impression he didn't. Andrew Alexander Einstein did loathe the idea that physical processes could be random. The physicist Niels Bohr, one of quantum physics' strongest proponents, once retorted the quote you mentioned with, "Einstein, stop telling God what to do!" In 1930, Bohr forced Einstein, through a thought experiment, to accept the uncertainty principle of quantum mechanics. Einstein tried unsuccessfully for the remaining 25 years of his life to show that the world behaves predictably.—E. Klarreich
To subscribe to Science News (print), go to https://www.kable.com/pub/scnw/ subServices.asp. To sign up for the free weekly e-LETTER from Science News, go to http://www.sciencenews.org/pages/subscribe_form.asp. References: Lumley, T. 2004. Sustainable sources of randomness. Chance 17(Spring):52-54. Further Readings: Goldberg, I., and D. Wagner. 1996. Randomness and the Netscape browser. Dr. Dobb's Journal (January). Available at: http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html. Hayes, B. 1993. The wheel of fortune. American Scientist 81(March/April):114-118. Klarreich, E. 2004. Toss out the toss-up: Bias in heads-or-tails. Science News 165(Feb. 28):131. Available at http://www.sciencenews.org/articles/20040228/fob2.asp. Peterson, I. 2004. A catalog of random bits. Science News Online (Oct. 16). Available at http://www.sciencenews.org/articles/20041016/mathtrek.asp. ______. 2003. The bias of random-number generators. Science News Online (Sept. 27). Available at http://www.sciencenews.org/articles/20030927/mathtrek.asp. ______. 2001. Lava lamp randomness. Science News Online (May 5). Available at http://www.sciencenews.org/articles/20010505/mathtrek.asp. ______. 1997. Lava lamp randomness. Science News 152(Aug. 9):92. ______. 1992. Monte Carlo physics: A cautionary lesson. Science News 142(Dec. 19 & 26):422. Sources: Mads Haahr Thomas Lumley Landon Noll Gregoire Ribordy David Wagner John Walker |
|||||||||
http://www.sciencenews.org/articles/20041204/bob9.asp |
|||||||||
From Science News, Vol. 166, No. 23, Dec. 4, 2004, p. 362. |
|||||||||
Copyright (c) 2004 Science Service. All rights reserved. |
|||||||||
