How the 'Luhn formula' validates credit card numbers
Think of it as your card's Da Vinci Code
Did you know your credit card has a Da Vinci Code?
It's true: Those seemingly random raised numerals on your card not only contain the account identifiers that banks and merchants need to transact business on your behalf, but a little-known credit card version of the Da Vinci Code that verifies its validity without the aid of computers.
"It's pretty cool that something that was developed pre-computer is still in use today. I think that's really important," says Derrick Niederman, a MIT-educated mathematician, New York Times crossword puzzle creator and author of many recreational mathematics books, including "Number Freak."
Even cooler, the code is cryptically hidden within the sequence of the card numbers themselves.
What's in your wallet, Dan Brown?
This low-tech mathematical sleight-of-hand, dubbed the "Luhn formula" after its inventor Hans Peter Luhn, played a tangential role in the development of the World Wide Web, search engines such as Google, text messaging and other high-tech wonders that make modern life a whirl.
Perhaps equally important at happy hour, every credit, debit and ATM card on earth still contains this mind-blowing bar trick worthy of the Beer Pong Hall of Fame.
Go ahead, test drive the Luhn formula here, using fake digits from the bogus card below. Click the first button to enter the fake digits:
Now, print out this Luhn formula PDF and test your own credit or debit card number.
Cool, right? Want to know how, and more importantly why, it works?
Prepare to become a Luhn-atic.
Check number, please!
In the unlikely event that you've given any thought at all to your credit card number, you probably view it as merely a series of random numerals: 16 digits on Visa, MasterCard and Discover cards, 15 on American Express cards, and 14 on Diners Club/Carte Blanche cards.
On a 16-digit card, the first six numerals identify the card issuer and the next nine numerals are the card account number (AmEx uses an eight-digit account number). My colleague Jeremy Simon has explained the meanings of these card numbers in more detail.
But there is absolutely nothing random about the final digit of your credit or debit card number. It has been appended as a "check number" or "key" to verify that the card is valid. It's this check number that gives the Luhn formula its Da Vinci Code allure.
When a card number is generated using Luhn's algorithm, various combinations of the digits on the card must ultimately add up to a number that is perfectly divisible by 10. For this reason, Luhn's formula is also referred to as "modulus 10" or "mod 10" for short. Change any digit or transpose nearly any two digits and the Luhn check will catch it.
"At its essence, an algorithm is a mechanizing device. It's a machine of sorts," says Niederman. "It allows you to push stuff out by application. Taken to its logical conclusion, the world of computing is built on algorithms. You can take a problem that seems intractable or vague and mechanize it and it ends at some point."
The Luhn formula was designed to instantly detect accidental data entry errors (missed keystrokes, transpositions, etc.) and not as a defense against fraud. It doesn't identify where an invalid number went sideways, it simply flags it as nonconforming.
Luhn checking won't tell you anything about the underlying card account itself. Nor should it be confused with Card Verification Value (or CVV) codes, those extra, un-embossed numbers on major credit cards that attempt to verify that the physical card is (or has been) in your possession.
In addition to its use in generating credit card numbers, the Luhn formula can be found in a wide range of numeric applications, from the IMEI cards in cell phones to the 10-digit National Provider Identifier issued to Medicare providers. It's even included in the ISO/IEC 7812 international standards that govern credit, debit, ATM, security and identification cards.
Thread counts and keywords
Luhn, who died in 1964, wasn't hunting for the first "killer app" in the credit card world. In fact, when the German-born IBM scientist proposed his formula in 1954, credit cards hadn't even been invented yet. Luhn's formula would later be included as the sum-check for a hand-held mechanical reader, for which he received a patent in 1960.
A former assistant manager of a textile mill, Luhn spent the 1930s and '40s as an engineering consultant to that industry. His Lunometer, a simple ruler-like tool that visually measures the thread and line count in fabrics, is still in use today. It's one of more than 80 patents that Luhn earned during his lifetime that include a computing gas pump, a cocktail recipe organizer (during Prohibition, no less), an inexpensive foldable raincoat and a forerunner to American Airlines' Sabre reservation management system.
After joining IBM in 1941, Luhn pioneered fundamental concepts in business information retrieval, including Key Words in Context (KWIC) and selective dissemination of information (SDI). Those breakthroughs laid the groundwork for such ubiquitous computer processes as keyword search, e-mail, instant messaging and RSS feeds, to name just a few.
First line against fraud
Although its original intent was to identify human error back in the pre-computer days of manual data entry, the Luhn check remains a valuable first line of defense against credit card fraud today.
If the card numbers don't tumble correctly through the algorithm (now computed literally faster than the blink of an eye), the transaction will be halted automatically before it even reaches the card issuer for authorization. Chances are excellent that the next line of anti-fraud software would net any fishy card numbers that do manage to slip through the Luhn check.
"For fraud, you have two choices: taking someone else's number or making one up. Luhn didn't know about that type of thing, but his algorithm still helps solve it," says Niederman. "If you were ordering something online, it obviously would be nice to give somebody else's number, but that doesn't work."
See related: The meanings of card numbers, Interactive: How credit card transactions work, The anatomy of a credit card
Published: June 4, 2010
Three most recent Innovations, features, new products stories: