The Luhn Algorithm for Credit Card Validation
The Luhn algorithm is a simple, public domain checksum algorithm that can be used to validate a variety of identification numbers. Invented in 1954 by an engineer at IBM, the Luhn algorithm has since been adopted as a standard by all major credit card issuers, as well as many government IDs, and is specified in ISO/IEC 7812-1.
The Luhn checksum works by calculating a check digit on the partial account number, which is then included as the last (rightmost) digit of the full account number. Therefore, when presented with any Luhn-verifiable account number, you can check for errors or transpositions by following the verification algorithm described below. But first, we'll discuss how the Luhn check digit itself is calculated.
How to calculate a Luhn checksum
- From the rightmost digit (the check digit), move left and double the value of every second digit; if doubled number is greater than 9 (e.g., 7 × 2 = 14), then subtract 9 from the product (e.g., 14: 14 - 9 = 5).
- Sum of all the digits in the newly calculated number.
- Multiply the sum by 9, the Luhn check digit is the rightmost digit of the result (e.g, the result modulo 10).
In the following example, we use a sample credit card number "7992739871", with an unknown Luhn check digit at the end, displayed as 7992739871x:
|Double every other||7||18||9||4||7||6||9||16||7||2||x|
The sum of all the digits in the third row above is 67+x.
We still need to calculate the check digit, X. The check digit can be obtained by computing the sum of the non-check digits then computing 9 times that value modulo 10. For our example, the equation is 67 × 9 mod 10. Broken down in more detail:
- Compute the sum of the non-check digits (67).
- Multiply by 9 (603).
- The units digit (3) is the check digit. Thus, x=3.
Verifying a card number with a Luhn checksum
The process of verifying if a credit card number is valid according to the Luhn algorith is simple. After carrying out steps 1 (doubling every second digit from the right and subtracting 9 if result is > 9) and 2 (summing all digits, this time including the check digit), you can determine if the number is Luhn valid as follows:
If the sum from step 2 modulo 10 is equal to 0 (e.g., if the total ends in zero) then the number is valid according to the Luhn formula. Otherwise, the number is not valid.
Effectiveness of the Luhn formula
The Luhn algorithm is highly effective considering its simpleness, and is able to detect any single-digit errors and mst transpositions of adjascent digits. There are a few scenarios where invalid transpositions to a number would still be calculated as Luhn valid (such as transposing a "33" with a "66", etc).
However, the Luhn algorithm is more than powerful enough to catch most causual errors that will be encountered when working with credit card numbers. You can see the formula in action at our credit card validation tool, which uses the Luhn formula.
Using the Luhn formula
Since the Luhn algorithm was initially developed to be calculated by a mechanical device, it can be compressed to as little as 1-2 lines in most modern programming languages. Here is an example Luhn implementation in Python:
def luhn(n): r = [int(ch) for ch in str(n)][::-1] return (sum(r[0::2]) + sum(sum(divmod(d*2,10)) for d in r[1::2])) % 10 == 0
You can find more implementations of the Luhm algorithm on our developer page.