Mathematics Makes Communication Possible

MAA Distinguished Lecture: “Pure” Math Finds Digital Age Application

Coding theorist Judy Walker (University of Nebraska–Lincoln) calls a CD player a “Reed-Solomon decoder.” As in: “Even my brand new car still has a Reed-Solomon decoder in it.”
Whether you’re spinning Faith Hill, Flogging Molly, or the Fab Four, see, your compact disc can deliver your music with fidelity—minor scratches and random read errors be damned—thanks to a type of error-correcting code introduced by Irving S. Reed and Gustave Solomon in 1960.

And as Walker explained on September 17 in her MAA Distinguished Lecture “Mathematics Makes Communication Possible,” the CD is not an isolated example: From flash drives to iPhones to internet banking, applications of number theory and algebraic coding theory make the modern world tick.
Which, given the perceived purity of these fields, might come as a surprise.

Unsullied by Any Application?

As Walker reminded those gathered in the MAA Carriage House, number theory is known for statements that are easy to understand but difficult to prove, beautiful in their simplicity but not of any obvious practical use. Think the twin prime conjecture or Fermat’s last theorem or Goldbach’s conjecture. 

Far from agonizing over whether it’s worth pursuing mathematical researches if they have no foreseeable utility, Leonard Eugene Dickson (1874-1954) celebrated his field’s detachment from the real world: “Thank God that number theory is unsullied by any application,” he wrote.

And even as late as 1971, communication theorists convening in Florida for a workshop doubted that their ivory tower musings would ever affect—or even interest—anyone outside their circle.
In a session on coding—i.e., techniques used for controlling errors in data transmission over unreliable or noisy communication channels—researchers voiced bleak assessments of their work’s value.     

“Everyone’s working on the same small set of problems, and the problems aren’t that important anyway,” said one attendee.

“No one else cares,” declared another. “It’s time to see this perversion for what it is.”

Both Dickson and the Florida workshoppers were wrong, of course, for reasons Walker enlisted the help of computer scientist Donald Knuth to verbalize. According to Knuth, “virtually every theorem in elementary number theory arises in a natural, motivated way in connection with the problem of making computers do high-speed numerical calculations.” 

In today’s digital age, in other words, mathematical puzzles are more than mere stimulants of intellectual curiosity. They are problems we must solve—if we want our wireless routers to work, anyway, and our credit card information to remain secure.

Securing Your Digits    

The security of online commerce rests on so-called public key cryptosystems. Walker cast her explanation of the concept with some perhaps familiar characters.

Suppose a number of individuals—Alice (of Wonderland fame), Aladdin, Arthur the aardvark, Angelina Ballerina, Amelia Bedelia—all want to communicate confidentially with Bob Newhart, but Oscar the Grouch poses a continual threat: He wants to intercept and read the messages. A public key cryptosystem functions like a locked mailbox: Any of the aforementioned A-listers can drop a message through the slot (i.e., encrypt a message) but only the intended recipient, Bob, has the key needed to open the box (i.e., decrypt) and read the message.

The most widely used public key cryptosystem today—RSA—is based on elementary number theory. 

Understanding exactly why RSA works requires a grasp of mathematics which, while not too heavy—just some modular arithmetic, Fermat’s Little Theorem, and Euler’s generalization thereof—this, er, margin is nonetheless too narrow to contain. 

Suffice it to say that RSA works due to some basic facts about large numbers: Generating large primes and multiplying them together is easy, but, as Walker stressed, “factoring large numbers is really really hard, like officially hard, officially hard in the computer science sense of hard.”

At least for now.

The advent of quantum computers, Walker explained, would change the facts. Quantum computers would make factoring large numbers easy.

“So if quantum computers come around before changes are made in Amazon’s protocol, for example, do not buy anything,” Walker warned her Carriage House audience. “Don’t do it.”

Post-Quantum Cryptography

While Walker ominously observed that “the people who are very into cryptography are starting to get very nervous about internet banking and using credit cards online,” she also outlined a cryptosystem that offers hope for a future full of worry-free e-commerce. 

Developed in 1978 by Robert McEliece, the McEliece cryptosystem relies on the hardness of decoding a general linear code. Because it requires the storage and manipulation of large matrices—rather than large individual numbers—the McEliece system has not been adopted on anything near the scale of RSA. 

Its day may come, however.

“At least as of this moment, in the public domain, there is no even quantum attack known that makes the McEliece system insecure,” Walker said. “That makes the McEliece system a candidate—a leading candidate, in fact—for post-quantum cryptography.” —Katharine Merow