Kids Code & Computer Science

How can you tell if a credit card number is valid or invalid? Meet the Luhn algorithm, one of many checksums helping us keep the internet in order.

Credit and debit cards are used in approximately 75% of transactions in the United States. At stores and restaurants, the cards are typically swept through a small electronic device or their chip is inserted. But when those card-reading devices fail, or when we make purchases online, a person actually types the card number into the computer. And sometimes the person typing might make a mistake.

Imagine entering a credit card number into an online store and due to the slip of a finger, midway through typing the number, one enters 72 instead of 27. With all the credit card numbers that exist in the world, perhaps there is one that actually corresponds to this mistyped number. Maybe that mistyped number belongs to one of your parent’s cards, and the person who typed it just accidently charged $600.00 to their account. With all the online transactions that happen every day, accidents like this must happen all the time right? Actually, there is a clever algorithm that prevents almost all such accidents. The algorithm is known as the Luhn Algorithm.

The Luhn Algorithm is one of many checksum algorithms. As the name implies, a checksum involves a relatively quick check involving the sum of the digits on the card. And this particular checksum was created by a computer scientist and avid inventor by the name of Hans Peter Luhn in 1954 (patented in 1960). Imagine the scenario following:

A well-intentioned shopper has a credit card with the following number: 79927398713 (this number is made up as we wouldn’t want to publish a real credit card number). However, the shopper gets distracted when entering the card number, and transposes the 2 and 7, typing the following incorrect number: 79972398713. Thanks to the Luhn algorithm, the computer immediately gives the user an error message, even before asking for the expiration date and three digit card verification value.

How does this algorithm work? First it takes every other digit that is entered and doubles it.

The original number (typed incorrectly):

First becomes:

If the result of doubling a digit is a two digit number (such as 18, 14, and 16 above), replace the result with the sum of the digits (1 + 8, 1 + 4, and 1 + 6).

Now add up all the the digits: 7 + 9 + 9 + 5 + 7 + 6 + 9 + 7 + 7 + 2 + 3 = 71.

In order for the computer to believe that the number entered could be valid, this sum must be divisible by ten (with a remainder of zero). However if we divide 71 by 10, the remainder is one. This alerts the computer that the number entered could not possibly be a valid card number.

If we go through the same algorithm with the correct card number we get the following result:

Taking the sum of the digits in the bottom row, we get 7 + 9 + 9 + 4 + 7 + 6 + 9 + 7 + 7 + 2 + 3 = 70. Indeed, 70/10 has a remainder of zero!

Does a sum that is a multiple of ten guarantee that the user entered the correct number? No. There are a few possible errors that would still result in a sum that is divisible by ten. Transposing 90 to get 09, or typing 22 instead of 55 (know as a “twin error”) are two possible errors that would pass the test of the Luhn algorithm. Can you think of the other two twin errors that would slip though the test?

Partly because the Luhn algorithm is not perfect, online stores also ask for the the card’s expiration date and the card verification number. However, using this quick checksum algorithm goes a long way in catching unintentional errors that might otherwise lead to accidently charging the wrong card.

Learn More

Peter Luhn and the history of his algorithms and inventions

https://spectrum.ieee.org/tech-history/silicon-revolution/hans-peter-luhn-and-the-birth-of-the-hashing-algorithm

Checksum algorithms

https://www.youtube.com/watch?v=RFOGDY2e0mQ

Wikipedia Luhn Algorithm

https://en.wikipedia.org/wiki/Luhn_algorithm