Luhn Check

The Luhn check is a checksum used by payment card numbers and many other identifiers. The last digit of the number is chosen so that a simple weighted digit sum comes out divisible by 10. Hans Peter Luhn of IBM devised it, and it is in the public domain. Its purpose is to catch typing mistakes. It is not a security mechanism and does not show that a number belongs to a real account.

The algorithm

To test a number, read its digits from the right, starting with the check digit as position 0:

1. Leave the digits in even positions (0, 2, 4, …) unchanged.
2. Double the digits in odd positions (1, 3, 5, …). If a doubled value exceeds 9, subtract 9 (equivalently, add its two digits).
3. Add everything. The number passes if the sum is divisible by 10.

Traced for the standard test number 4111111111111111: reading from the right, the processed digits are 1, 2, 1, 2, …, 1, 2, 1, 8 (the leading 4 is doubled to 8), which sum to 30. Since 30 is divisible by 10, it passes.

To generate a check digit, compute the sum over the body with the check digit set to 0 and choose the digit that brings the total to a multiple of 10. For the body 411111111111111 that digit is 1.

def luhn_ok(digits: str) -> bool:
    total = 0
    for i, ch in enumerate(reversed(digits)):
        d = int(ch)
        if i % 2 == 1:
            d *= 2
            if d > 9:
                d -= 9
        total += d
    return total % 10 == 0

What it detects

In a test on 2,000 random 16-digit numbers constructed to pass the check:

• Single-digit errors: of 288,000 single-digit changes, none passed. Doubling is why: any change to a digit changes the sum by an amount not divisible by 10, in both the doubled and the undoubled positions.
• Adjacent transpositions: of 27,024 swaps of two different neighbors, 571 (2.1%) still passed. All of them were swaps of 0 and 9, which the weighting cannot distinguish.

Other rare patterns, such as certain twin errors, also escape. The design target was accidental keystroke mistakes, and for those it is very effective.

Why it helps PII detection

Detecting card numbers in free text with a pattern such as "13 to 19 digits, possibly with spaces or hyphens" matches many things that are not cards: tracking numbers, order ids, phone numbers, timestamps. A random digit string passes the Luhn test with probability about 1 in 10 (measured: 0.0998 over 200,000 random 16-digit strings). Adding the check therefore removes roughly 90% of random false matches before redaction or alerting, which cuts noise and avoids destroying legitimate identifiers.

What it does not do

• It does not prove validity. About one in ten arbitrary digit strings passes, and anyone can compute a passing number, so a passing number may not be a card at all. Validity requires the issuer.
• It gives no protection against fraud. The algorithm is public, so a fabricated number with a correct check digit is trivial to make.
• A failing check does not prove a string is not a card number in text. A typo in the source, or digits split by line breaks, can make a real number fail. A detector that must not miss real numbers can flag pattern matches that fail Luhn at lower severity instead of dropping them.
• The check says nothing about the length or issuer prefix; those are separate rules.

In a redaction pipeline, treat the Luhn result as a precision filter on a pattern match, not as a classifier on its own.

References

• Wikipedia, Luhn algorithm