Luhn Algorithm Explained: Credit Card Validation

History: Hans Peter Luhn

Hans Peter Luhn was a German-American IBM scientist who invented the algorithm in 1954 — fifteen years before the widespread adoption of credit cards. He wasn't designing it for payments; he was solving a general problem: how do you quickly verify that a number typed by a human is correct?

Before computers were ubiquitous, identification numbers were written down, called over the phone, and manually typed into machines. Transcription errors were common. A checksum that could catch most single-digit mistakes and transpositions — using nothing more than basic arithmetic — was genuinely valuable.

Luhn filed a patent in 1954, and IBM published the algorithm into the public domain, making it available to anyone. When credit card networks started standardizing in the 1970s and 1980s, they adopted Luhn as the validation standard. Today it's defined in ISO/IEC 7812-1, the international standard for identification cards.

The algorithm has been in continuous use for 70 years, outlasting countless computing paradigms. Its longevity is a testament to one design principle: solve the problem in front of you as simply as possible.

How the Algorithm Works

Luhn is a weighted checksum. It processes digits from right to left, doubling every second digit, then sums everything. If the total is divisible by 10, the number is valid.

The three-step logic:

1. Starting from the rightmost digit, moving left: keep every odd-positioned digit (positions 1, 3, 5...) and double every even-positioned digit (positions 2, 4, 6...).
2. If doubling produces a number greater than 9: subtract 9 (or equivalently, sum the two digits of the result).
3. Sum all values. If the total mod 10 equals 0, the number is valid.

For digits d1 d2 d3 ... dn (right to left):

position 1 (rightmost): keep as-is
position 2: double, subtract 9 if > 9
position 3: keep as-is
position 4: double, subtract 9 if > 9
...

sum = d1 + f(d2) + d3 + f(d4) + ...

where f(x) = x*2       if x*2 <= 9
             x*2 - 9   if x*2 > 9

Valid if: sum % 10 === 0

Why Double Alternating Digits?

The weighting is what catches transposition errors. If you swapped two adjacent digits in a plain sum, the total would be the same (addition is commutative). By assigning different weights to alternating positions, swapping two adjacent digits almost always changes the sum.

The one exception Luhn misses: swapping 0 and 9. Both 09 and 90 produce the same weighted sum because 9 doubled is 18, minus 9 is 9 — same as 9 kept. This is a known limitation.

Step-by-Step Walkthrough

Let's validate the classic test Visa number: 4111 1111 1111 1111

Write out the digits and number their positions from right to left:

Example with Doubling Past 9

For a digit of 7 in a doubling position:

7 × 2 = 14
14 > 9, so: 14 - 9 = 5

Equivalently: 1 + 4 = 5 (sum the digits of the doubled value)

More examples:
5 × 2 = 10 -> 10 - 9 = 1
8 × 2 = 16 -> 16 - 9 = 7
9 × 2 = 18 -> 18 - 9 = 9

Detecting an Error

Change the last digit from 1 to 2: 4111 1111 1111 1112

Position 1 (keep) is now 2 instead of 1. Sum becomes 31. 31 mod 10 = 1, not 0. Invalid — the typo is caught.

Generating Check Digits

You have a partial number and need to calculate the correct check digit to append. The process:

1. Take your number without the check digit (n−1 digits)
2. Append a 0 as a placeholder
3. Run Luhn on the full number, get the sum
4. Check digit = (10 - (sum % 10)) % 10
5. Replace the 0 with this digit — the complete number now passes Luhn

Example: Generate check digit for Visa base number 411111111111111

Step 1: Number without check digit: 411111111111111 (15 digits)
Step 2: Append 0: 4111111111111110 (16 digits)
Step 3: Run Luhn on 4111111111111110

Positions (R->L): 0(keep), 1(x2->2), 1(keep), 1(x2->2), ... 4(x2->8)
Sum = 0+2+1+2+1+2+1+2+1+2+1+2+1+2+1+8 = 29

Step 4: (10 - (29 % 10)) % 10 = (10 - 9) % 10 = 1

Step 5: Replace the trailing 0 with 1
Result: 4111111111111111

Credit Card Number Structure

The 15–19 digits of a credit card number aren't random. They encode information about the issuing network and account.

4 1 1 1  1 1 1 1  1 1 1 1  1 1 1 1
|  BIN        Account number      |
|                                 +- Check digit (Luhn)
+- MII (Major Industry Identifier)

MII: Major Industry Identifier (First Digit)

IIN/BIN: Issuer Identification Number (First 6–8 Digits)

The first 6 digits (IIN, also called BIN — Bank Identification Number) identify the issuing institution. With 8-digit BINs now standardized by ISO 7812, there are 10⁸ = 100 million possible BINs, accommodating the growth of card issuers globally.

The Account Number and Check Digit

After the IIN, the remaining digits (except the last) are the account number assigned by the issuer. The last digit is always the Luhn check digit. The total length (including check digit) ranges from 12 to 19 digits depending on the network.

JavaScript and Python Code

JavaScript

/**
 * Validate a number using the Luhn algorithm.
 * Accepts strings with spaces and hyphens (e.g., "4111-1111-1111-1111").
 */
function luhnValidate(input) {
  const digits = String(input).replace(/\D/g, '');
  if (digits.length < 2) return false;

  let sum = 0;
  let isSecond = false;

  for (let i = digits.length - 1; i >= 0; i--) {
    let digit = parseInt(digits[i], 10);

    if (isSecond) {
      digit *= 2;
      if (digit > 9) digit -= 9;
    }

    sum += digit;
    isSecond = !isSecond;
  }

  return sum % 10 === 0;
}

/**
 * Generate the Luhn check digit for a partial number.
 * Pass the number WITHOUT the check digit.
 */
function luhnCheckDigit(partial) {
  const digits = String(partial).replace(/\D/g, '') + '0';
  let sum = 0;
  let isSecond = true; // appended 0 is position 1 (keep), so position 2 doubles first

  for (let i = digits.length - 1; i >= 0; i--) {
    let digit = parseInt(digits[i], 10);

    if (isSecond) {
      digit *= 2;
      if (digit > 9) digit -= 9;
    }

    sum += digit;
    isSecond = !isSecond;
  }

  return (10 - (sum % 10)) % 10;
}

/**
 * Detect card network from card number prefix.
 */
function detectCardNetwork(number) {
  const n = String(number).replace(/\D/g, '');
  if (/^4/.test(n))                 return 'Visa';
  if (/^5[1-5]/.test(n))            return 'Mastercard';
  if (/^2[2-7]/.test(n))            return 'Mastercard';
  if (/^3[47]/.test(n))             return 'Amex';
  if (/^6(?:011|5)/.test(n))        return 'Discover';
  if (/^35(?:2[89]|[3-8])/.test(n)) return 'JCB';
  return 'Unknown';
}

// Usage
console.log(luhnValidate('4111 1111 1111 1111')); // true
console.log(luhnValidate('4111 1111 1111 1112')); // false (last digit wrong)
console.log(luhnCheckDigit('411111111111111'));   // 1
console.log(detectCardNetwork('4111111111111111')); // "Visa"

Python

def luhn_validate(number) -> bool:
    """
    Validate a number using the Luhn algorithm.
    Accepts strings with spaces or hyphens.
    """
    digits = [int(c) for c in str(number) if c.isdigit()]
    if len(digits) < 2:
        return False

    checksum = 0
    for i, digit in enumerate(reversed(digits)):
        if i % 2 == 1:  # every second digit from the right (0-indexed)
            digit *= 2
            if digit > 9:
                digit -= 9
        checksum += digit

    return checksum % 10 == 0


def luhn_check_digit(partial) -> int:
    """
    Calculate the Luhn check digit for a partial number.
    Pass the number WITHOUT the check digit.
    """
    digits = [int(c) for c in str(partial) if c.isdigit()] + [0]
    checksum = 0

    for i, digit in enumerate(reversed(digits)):
        if i % 2 == 1:
            digit *= 2
            if digit > 9:
                digit -= 9
        checksum += digit

    return (10 - (checksum % 10)) % 10


def detect_card_network(number: str) -> str:
    """Identify the card network from the card number prefix."""
    import re
    n = re.sub(r'\D', '', str(number))
    if n.startswith('4'):
        return 'Visa'
    if re.match(r'^5[1-5]', n) or re.match(r'^2[2-7]', n):
        return 'Mastercard'
    if re.match(r'^3[47]', n):
        return 'Amex'
    if re.match(r'^6(?:011|5)', n):
        return 'Discover'
    return 'Unknown'


# Usage
print(luhn_validate('4111 1111 1111 1111'))   # True
print(luhn_validate('4111 1111 1111 1112'))   # False
print(luhn_check_digit('411111111111111'))    # 1
print(detect_card_network('4111111111111111')) # 'Visa'

Performance Note

Luhn runs in O(n) time where n is the number of digits. For card numbers this is always a small constant (max 19 digits), so performance is never a concern. The bottleneck in payment forms is network latency to your payment processor, not client-side validation.

Uses Beyond Credit Cards

IMEI Numbers

Every mobile phone has a 15-digit IMEI (International Mobile Equipment Identity). The last digit is a Luhn check digit. You can verify yours by dialing *#06# on your phone and checking the last digit against the Luhn algorithm.

# Example IMEI: 356938035643809
# Last digit (9) is the Luhn check digit
luhn_validate('356938035643809')  # True

National Provider Identifier (NPI)

In the US healthcare system, every provider has a 10-digit NPI. The check digit (digit 10) uses a modified Luhn algorithm where the base number is prefixed with "80840" before calculation. This prefix is part of the ISO 7812 healthcare industry prefix.

// NPI Luhn validation (prefix "80840" is prepended)
function validateNPI(npi) {
  const prefixed = '80840' + String(npi).replace(/\D/g, '');
  return luhnValidate(prefixed);
}

Canadian Social Insurance Number (SIN)

Canada's 9-digit SIN uses a standard Luhn check on the full 9 digits. The third digit identifies the province of issuance (1 = PEI, NS, NB; 2 = QC; etc.).

Other Uses

• Israeli ID numbers: 9-digit national ID
• Greek Social Security (AMKA): 11-digit number
• South African ID numbers: 13-digit national ID
• UnionPay (China): Interbank Card Association card numbers
• Gift card numbers: Many retailers use Luhn for their card systems
• ISIN (International Securities Identification Number): Uses a variant of Luhn

Limitations and What Luhn Can't Do

Errors It Misses

• 09 to 90 transpositions: The only adjacent swap that produces the same Luhn sum. Rare in practice.
• Two-digit errors: Any combination of errors that happen to cancel out (e.g., one digit too high and another too low by the same amount) can slip through.
• Intentional construction: Anyone can generate a number that passes Luhn. The algorithm is public domain and trivial to implement.

Not a Security Measure

This bears repeating because it's frequently misunderstood: a valid Luhn number proves nothing about the card's legitimacy, availability, or ownership. It only indicates the number was typed without the specific types of errors Luhn catches.

Verification vs Validation

Luhn validation (does the number follow the checksum format?) is different from card verification (does this card exist, is it active, does the user own it?). Client-side Luhn validation catches typos before you make an API call to your payment processor. The payment processor handles actual verification. Run Luhn for UX; don't rely on it for anything security-related.

The 70-Year Design

Luhn was designed for mechanical systems — simple enough to verify by hand or with minimal computing. By modern cryptographic standards it's trivially simple. But "trivially simple" is exactly what was needed: a global standard that any system in 1970, 1990, or 2026 can implement with a few lines of code. That's why it's still here.