news

Science | DOI: 10.1145/1924421.1924427
Gary Anthes
the Quest for
Randomness
It’s not easy to generate a string of numbers that lack any pattern
or rule, or even to define exactly what randomness means.

GEnERATInG RAndom num- BERS might seem pretty simple. After all, so many things in our everyday lives occur without pattern or repetition—coin tosses, for example, or the distribution of raindrops on your car windshield. In any case, the whole notion of striving for randomness might seem a bit alien to a computer scientist, who is trained to make processes predictable and repeatable.

IllustratIon by weknow/shutterstock

Cryptographers use random number generators (RNGs) to produce unpredictable keys for coded messages, digital signatures, challenge-response systems, and other technologies at the heart of information security. And researchers in fields such as biology, economics, and physics use them to simulate the real world via Monte Carlo models. Human life and great sums of money may depend on the robustness of these systems, yet it is often difficult to prove that they work correctly—and will continue to do so.

Part of the problem is one of definition. One might say, for example, that a random bit generator (as RNGs are often called) must over time produce half 0s and half 1s, or that it must gen-

erate the sequence “00” one-quarter of
the time. But, points out Silvio Micali,
a computer scientist and cryptography
expert at Massachusetts Institute of
Technology (MIT), the sequence 0, 1,
2, ... 9 (written in binary) would pass
those tests but would hardly be consid-
ered “random.”
Definitions matter, Micali says. “If
you define [randomness] correctly,
then you can get it. But if you are vague
or unclear, you can’t possibly get it.”
In 1984, Micali and Manuel Blum, a
professor of computer science at Carn-
egie Mellon University, published an
influential paper, “How to Generate