No. 3020: ERROR DETECTION

by Andy Boyd

Click here for audio of Episode 3020

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.

keyboard
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.

credit card
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