Algorithm Spotlight: The Luhn Algorithm

5 min readMay 26, 2018

Picture this: You are shopping for some of the latest clothes or the trendiest gadgets, on your favorite e-commerce site. You finish adding all the items in the cart you desired for, and you are about to check out when suddenly, the e-commerce sites asks you for your most important 16-digit number needed to complete the transaction. Without thinking twice, you pull out your credit card. As you type down your credit card number on the screen, have you ever wondered how the website knows that your card number is legitimate and that you are not making up the number?

Well, I am about to answer this right now. But first, let’s go through the possible ways that this could work. As far as I know, there are two ways to verify legitimacy of a credit card:

Search every credit card number to ever exist.
Use some crazy math algorithm (which may actually be much easier than you think)

Let’s look at the first possibility: Comparing your credit card number with every other credit card number in a database. It seems pretty straightforward, right? An array of credit card numbers like this: arr = [“xxxx xxxx xxxx xxxx”, “xxxx xxxx xxxx xxxx”, …] and then a nested for-loop like this:

string inputCreditCard = “xxxx xxxx xxxx xxxx”

for (int i = 0; i < arr.size(); i++) {

— — — for (int j= 0; j< 16; j++) {

— — — — — if (arr[i][j] != inputCreditCard[j]) → return false;

— — — }

}

return true;

Well, it turns out it is not that straightforward. In fact, there are several glaring problems with this method. The first is obvious: No credit card company, government, or other number issuing organization would ever be willing to provide an e-commerce site with all of its registered numbers. It’s simple common sense. Second, in a hypothetical universe, even if CC companies would give access to all its numbers, comparing digit by digit, for every single CC number out there, is time consuming. There are 16 digits in a credit card. Each digit has ten possible values. That’s literally 10¹⁶ different possible credit cards out there. The worst case runtime for parsing through all these credit cards is O(n). Quite simply, you would not want to wait for seconds, even minutes on end, for your credit card to be validated. You want it validated now, so you can go no to buying those new kicks or new smartphone.

Now onto the second possibility: The crazy math algorithm. It is a little bit more complex. But at least it runs in constant O(1) time. And it actually isn’t even that hard to code. Yes, you guessed it: I’m talking about the Luhn algorithm. And that is how credit cards are validated on shopping sites.

The Luhn algorithm was developed in the 1950s by Hans Peter Luhn at IBM. In his patent, he described a sort of mechanical computer that would verify official numbers that have a “check digit”, in which he quoted:

“The apparatus of my invention is used in a checking System for multi-digit numbers to indicate whether, in transmitting a number, an error has been made, such as a transposition of the digits.”

Today, it is primarily used to verify the legitimacy of a credit card number, but it was also designed to verify other ID’s, such as mobile phone IMEI numbers and even some nations’ SSNs. But in order to understand the algorithm, we first have to understand the anatomy of the credit card number. What do these 16 digits mean? What is the checksum? Where is the checksum? Take a look at the credit card diagram below, and I will explain everything:

MII — The Major Industry Identifier. Certain industries and companies use different MII numbers: AMEX uses 3, Visa uses 4, MasterCard 5, and Discover Card 6. The other numbers (1, 2, 7, 8, 9) are used by foreign credit card companies, bankcards, national governments, and other industries that issue cards.
BIN — The Bank Identification Number (otherwise known as Issuer Identification Number). This number verifies the CC company that issued your credit card, as well as specific features your card may have (e.g spending limits).
Account Number — This is the number of the user’s credit card account.
Checksum —This is the auxiliary digit used in the Luhn algorithm to help verify your credit card. The algorithm is, in a nutshell, taking the 15 other digits, calculating a new number from that, and comparing it with the Checksum digit. If these two digits are equal, then the credit card is valid.

The Luhn Algorithm goes as follows:

Reverse the digits of the CC
Starting from the second digit (the first digit after the checksum), double every alternating number (including the second digit)
Add these newly doubled alternating numbers to the rest of the digits
Take the remainder of that number divided by ten, this is your “validation” number
If the validation number is equivalent to the checksum, return true. Else, return false.

The pseudo code is available here:

bool isValid(string creditCardNumber)
{
    int sum = 0; 
    int checkSumDigit = creditCardNumber[15]; 
    reverseString(creditCardNumber);
    for (int i = 1; i < 16; i++)
    {
      if (i%2 == 1) -> sum += creditCardNumber[i]*2; 
      else -> sum += creditCardNumber[i]; 
    }
    int validation = sum%10; 
    return validation == checkSumDigit;
    
}

So that is basically it. The entirety of validating a credit card number is in this algorithm (well, plus a few extra security features that we won’t go into detail). The Luhn algorithm is primarily used for just checking that your inputted credit card number is correct and that you didn’t accidentally type a wrong digit or make up a fake CC number, and that is enough for your favorite e-commerce websites to validate your legitimate CC number. So, enjoy shopping and I hope you enjoyed what you just learned!

Sources:

Algorithm Spotlight: The Luhn Algorithm

Written by Chris Hailey