The Luhn Algorithm
January 28th, 2006 by SplineGuy
Here’s a question I’ve never asked before today but now I know the answer. When you are shopping online and you enter a credit card number into a form, how do they know that it is a valid credit card number? I always imagined that they were immediately checking the number against some database of valid credit card numbers and matching it against my address. That may be true in many cases but is not necessarily so. Most credit card companies employ a method of validating that a credit card number is authentic by method of the Luhn Algorithm, sometime called the modulus 10 algorithm.
In other words, not every 13 or 16 digit number can be a credit card number. I think I had figured out just through inspection that VISA cards start with a 4, Mastercards start with a 5, and Discover cards start with a 6 but the rest of the numbers must satisfy the following test:
1. Take the 1st, 3rd, 5th, 7th, etc. digits from left to right (the odd places). Double each of those numbers. If the value ends up larger than 9, then subtract 9 from it.
2. Then add all of these together with the numbers in the even places.
3. The result must be evenly divisible by 10 (i.e., have a zero in the ones place)
EX: 3205 3211 7082 0010
The odd places are 3, 0, 3, 1, 7, 8, 0, 1 which doubles to 6, 0, 6, 2, 14, 16, 0, 1. The two double digit numbers now need to have 9 subtracted from them resulting in the list 6, 0, 6, 2, 5, 7, 0, 1.
Now we place them back in the odd places resulting in the number: 6205 6221 5072 0020.
Now we sum up these digist 6 + 2 + 0 + 5 + 6 + 2 + 2 + 1 + 5 + 0 + 7 + 2 + 0 + 0 + 2 + 0 = 40.
Thus, this would be a valid credit card number. Note, by the way, that I made that number up and it is not anyone’s credit card number.
EX: Consider the same number with the first digit changed to 2. That is, 2205 3211 7082 0010. After the doubling step we have 4205 6221 5072 0020, which sums to 38 and thus is not a multiple of 10, so it cannot be a valid credit card number.
Problem (from think again!): The number 5439 3201 3232 3209 is not valid. Change the third digit from the left to make it valid.
The first four digits indicate the issuing bank as well as the type of card. Discover cards always begin 6011 since there’s only one bank for Discover. Likewise, American Express cards begin with 3. I forget the starting sequence: 3733? (it’s been a while since I’ve processed credit cards manually). All the issuers use the same validation system.
One nice thinggg about the system that the CC issuers use is that it catches digit transposition (23 instead of 32) as well as digit shift (e.g., typing 5 instead of 4 or 6). ISBNs use a different checksum scheme. IIRC, it’s multiply the first digit by 1, second by 2, etc. then add up all the products and take the answer modulo 11 (using X for 10) to come up with the check digit at the end of the ISBN..
Okay, but how does it know your experation date?
I guess they figure that out when they actually check it against the database containing your account information.
In Sweden every person is given a specific number when they are registered at the government (IE when you’re born).
This number is basically YYMMDD-XXXZ, where XXX is an area code of wher eyou where born, also, it’s odd for men and even women. It also applies the Luhn algorithm for calculating the Z.
This number is used for identification everywhere. So if you know the Luhn algorithm you can get in to like nightclubs and pubs. Since the guards only enter the number in to a machine whish says if it’s real or not you can easily make up you’re own numbers which will work.
Though, the last 20 years they have gotten more focused on people showing proof of their identification in form och ID-cards than just hearing the numbers.
That’s fascinating. I’ll have to share that with some of my classes. Since I’m pretty certain that none of our students visit night clubs in Sweden, I won’t feel guilty for letting them in on the secret.