beanz Magazine

Credit Card Algorithm

Marco Verch on Flickr

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):

7 9 9 7 2 3 9 8 7 1 3

First becomes:

7 18 9 14 7 6 9 16 7 2 3

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

7 9 9 5 7 6 9 7 7 2 3

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:

Original number 7 9 9 7 2 3 9 8 7 1 3
Double every other digit 7 18 9 14 7 6 9 16 7 2 3
Add the digits of two digit numbers 7 9 9 5 7 6 9 7 7 2 3

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

Also In The December 2018 Issue

Create colourful geometric patterns in SketchUp inspired by the Great Mosque of Cordoba.

Learn how to use animated GIFs to create proper animation loops in Scratch.

Create an electronic obstacle course and test the steadiness of your hands as you navigate through.

What’s allowed in an e-mail address? Let’s break down the syntax.

Throwing your old tech in the trash is bad for the environment. Check out some safer, cleaner alternatives.

New, crafty mods that’ll push your Minecraft design skills to new levels.

Part philosophical paradox, part coding puzzle, quines are sure to tease and challenge your brain!

5 questions with the designer pushing innovation in 3D printed clothes.

All work and no play makes it harder for kids to learn, especially those with anxiety and learning disabilities.

Dive into the nuts & bolts of storing pictures and files on your computer.

A clever AI is creating twisted, surreal art. Math or magic?

Two doors hide a zonk, and one door hides a prize. Can probability & statistics help you pick the right one?

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.

Learn about the Destination Dispatch algorithm and create your own robotic lift.

Grab your friends & disconnect from the digital world with these fun science & tech board games.

Interesting stories about computer science, software programming, and technology for December 2018.

Links from the bottom of all the December 2018 articles, collected in one place for you to print, share, or bookmark.