Sign In

Communications of the ACM


Pure Randomness Extracted from Two Poor Sources

Pure Randomness Extracted from Two Poor Sources, photo illustration

Credit: Dan Tilert

Truly random numbers are critical for computing and cryptography. Although deterministic algorithms can generate numbers that seem random, critical applications depend upon truly unpredictable physical processes. Unfortunately, the resulting sequences can still contain hidden regularities, so theoretical computer scientists have long sought "extractors" that produce perfect randomness from these imperfect sources.

It has been known for 30 years that there should be many ways to combine two imperfect sources to generate nearly perfectly random numbers, but only now have researchers shown explicitly how to create such "two-source extractors." The work, which received a best-paper award at the 48th ACM Symposium on Theory of Computing (STOC 2016) last June, brought together developments from several disparate areas of computer science. "The search has been going on mainly in the past 10 or 15 years, and this is the culmination of this effort," said Avi Wigderson of the Institute for Advanced Study at Princeton University in Princeton, NJ. "It's a huge jump, both technically and also quantitatively."


No entries found

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.