difficulty levels — click green to claim

> LUHN ALGORITHM

luhn difficulty: 1–3 invented: 1954, IBM inventor: Hans Peter Luhn

The idea in plain English: The Luhn algorithm (also called "mod-10") is a simple checksum formula used to validate identification numbers. Imagine writing down a credit card number — if you accidentally mis-type a single digit or swap two adjacent digits, the Luhn check will catch it. The algorithm works by scanning the digits from right to left, doubling every second digit, summing everything up, and checking that the total is divisible by 10. That final check digit isn't random — it's computed from all the other digits to make the total sum into a multiple of 10.

Why this really exists: Hans Peter Luhn, an IBM researcher, filed US Patent 2,950,048 in 1954 to create a simple, fast way to detect data-entry errors before computers could validate in real time. The algorithm catches any single-digit error (typing 5 instead of 3) and most adjacent digit swaps (typing 14 instead of 41). It's computationally trivial — no prime numbers, no encryption — which was essential for 1950s electromechanical tabulating machines. Today it's embedded in every credit card terminal, phone activating a SIM, and warehouse scanning an EAN barcode.

▸ Concrete Example

Let's verify the number 4532 0151 1283 0366 — a valid test PAN from the Visa test range. We'll follow the Luhn check algorithm step by step:

Step 1 — Remove spaces, write the digits right-to-left, index starting from the check digit:
Digits: 4 5 3 2 0 1 5 1 1 2 8 3 0 3 6 6
Positions: 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 ← position
Doubled: N Y N Y N Y N Y N Y N Y N Y N Y ← double pos 1,3,5,...

Step 2 — Iterate from position 1 (rightmost, the check digit):

Digit	Pos	Double?	Value	Contribution
6	1	No	6	6
6	2	Yes	12	1+2=3
3	3	No	3	3
0	4	Yes	0	0
3	5	No	3	3
8	6	Yes	16	1+6=7
2	7	No	2	2
1	8	Yes	2	2
1	9	No	1	1
5	10	Yes	10	1+0=1
1	11	No	1	1
0	12	Yes	0	0
2	13	No	2	2
3	14	Yes	6	6
5	15	No	5	5
4	16	Yes	8	8

Step 3 — Sum all contributions:
6 + 3 + 3 + 0 + 3 + 7 + 2 + 2 + 1 + 1 + 1 + 0 + 2 + 6 + 5 + 8 = 50

Step 4 — Is 50 divisible by 10? Yes! 50 mod 10 = 0.
✓ 4532 0151 1283 0366 is a valid Luhn number.

💡 Notice the check digit (rightmost 6) was not computed separately here — it's already part of the number. If we were generating a check digit, we'd calculate it so the sum becomes a multiple of 10.

▸ How to Validate (Step by Step)

1. Drop all non-digit characters (spaces, dashes)

2. Starting from the rightmost digit (position 1), double every digit in an even position (2, 4, 6, ... from the right)

3. If doubling a digit gives a two-digit result (e.g., 8×2=16), sum those two digits (1+6=7)

4. Add up all digits — the undoubled ones, the doubled ones (after digit-summing), and the check digit itself

5. If the total is divisible by 10 (total mod 10 == 0), the number is valid

# Python implementation:
def luhn_check(number_str):
    digits = [int(c) for c in number_str if c.isdigit()]
    total = 0
    for i, d in enumerate(reversed(digits)):
        if i % 2 == 1: # double every second digit
            d = d * 2
            if d > 9:
                d = d - 9 # same as summing digits
        total += d
    return total % 10 == 0

# Test it:
print(luhn_check("4532015112830366")) # True
print(luhn_check("4532015112830367")) # False (check digit wrong)

💡 The trick d - 9 works because summing the digits of any two-digit number (10–18) is the same as subtracting 9. For example, 16 → 1+6=7 = 16-9. Neat math shortcut!

▸ How to Generate a Check Digit

If you have the first 15 digits of a credit card and need to compute the 16th (the check digit):

1. Apply the Luhn algorithm to the 15 digits (as if the 16th digit were 0)

2. Let's say the sum is S. Compute: check_digit = (10 - (S mod 10)) mod 10

3. Append that digit. The full 16-digit number will always pass the Luhn check

def luhn_generate(partial):
    digits = [int(c) for c in partial if c.isdigit()]
    total = 0
    for i, d in enumerate(reversed(digits + [0])):
        if i % 2 == 1:
            d = d * 2
            if d > 9: d = d - 9
        total += d
    check = (10 - (total % 10)) % 10
    return partial + str(check)

▸ Real-World Applications

Credit/Debit card numbers: Every Visa, Mastercard, Amex, and Discover PAN includes a Luhn check digit — that's billions of cards
IMEI numbers: Every mobile phone's International Mobile Equipment Identity (15 digits) uses Luhn to catch typos during registration
Canadian Social Insurance Numbers (SIN): The 9-digit SIN uses a variant of the Luhn algorithm
ISIN codes: International Securities Identification Numbers (for stocks, bonds, ETFs) use Luhn for the check digit
EAN/UPC barcodes: The last digit of retail product barcodes is a Luhn check digit
US Selective Service: The registration acknowledgment number uses Luhn

▸ Limitations

Luhn is not cryptographic. It's designed to catch accidental errors, not intentional fraud. It will detect:

✅ All single-digit errors (e.g., 5→8)
✅ Most adjacent transpositions (e.g., 12→21) — but not all (09→90 slips through!)
❌ It does NOT detect arbitrary tampering or fraudulent number generation

A determined adversary can trivially produce valid Luhn numbers. The check digit protects against typos, not thieves.

← Back to all ciphers