No. 3020:
Error Detection
Audio

Today, the math behind credit cards. The University of Houston presents this series about the machines that make our civilization run, and the people whose ingenuity created them.

We've all done it at one time or another. We go to a website where we type in our credit card number, press the enter key, and are told the number's invalid. On closer examination, we realize we made a mistake typing. We fix the problem and the transaction goes through.

QWERTY Keyboard on a laptop computer. Photo Credit: Wikimedia Commons

So exactly how did the website know the card number was invalid? You might imagine it was sent off to the credit card company where it wasn't found. But that's likely not the case. The error was probably caught using a simple consistency check patented by Hans Peter Luhn in 1954.

Luhn grew up in Germany but as a young man came to the U.S. in the mid-1920s. He began his career in the textile industry, but showed such drive and creativity he was eventually hired as a senior research engineer at IBM. He went on to make seminal contributions in computer science, including the consistency check that bears his name.

Wrong digits. Transposed digits. Doubled digits. All common typing errors. To catch them the last digit in a credit card number is a check digit. When a financial institution issues a new credit card, the check digit isn't random. Instead, it's calculated using a formula that involves all the other digits. Jump forward to a time when you're entering your card number on a website. That same formula can be used to see if the check digit checks out. If not, you've entered an invalid card number.

An up close of a credit card. Photo Credit: Free Stock Photos

The process is an example of the more general field of study signal error detection.When we send information electronically it can get garbled along the way, for example, as the result of a bad wireless connection. Error detection methods not only send the desired information, but a means to check if the information arrived accurately. No detection method is perfect, but some are better than others. The tradeoff is a matter of complexity. The more effectively a method detects errors, the more time it takes to run. Good error detection is a matter of balancing effectiveness and time for the problem at hand.

In the case of typing credit card numbers, Luhn's method proves to be pretty good. Better methods have come along, but they're not sufficiently better to replace Luhn's, a method that's firmly established itself in the world of computer transactions. Luhn's method catches most of the common errors we make, and it's incredibly simple. You can find it online and use it to validate the check digits of your own credit cards in a matter of just a minute or two.

You can even create new, valid credit card numbers. They'll make it past basic error detection, but they aren't usable. That only happens when the number's actually been issued and you have related information like name and address. And you don't want to tempt fate. Attempting to use a false card number is, of course, illegal.

I'm Andy Boyd, at the University of Houston, where we're interested in the way inventive minds work.

(Theme music)

Check digits are used in many other contexts than credit cards. See, for example, https://en.wikipedia.org/wiki/Check_digit. Accessed August 25, 2015.

An excellent description of Luhn's method along with an example can be found at the Wikipedia website: https://en.wikipedia.org/wiki/Luhn_algorithm. Accessed August 25, 2015.

'Hans Peter Luhn, Mentor, 68, Dies.' New York Times August 20, 1964. See also: http://www.nytimes.com/1964/08/20/hans-peter-luhn-mentor-68-dies.html?_r=2. Accessed August 25, 2015.

This episode was first aired on August 27, 2015