The digits on your credit card aren't random. Neither are the 12 digits on your Aadhaar card. In both, one digit isn't data; it's a validity check on all the others.
This is the check digit problem. How do you design a number that can detect its own transcription errors before it ever hits a server?
Two algorithms solved it in different ways, for different reasons. Both are still running today.
The Problem With Numbers and Humans
Humans copy numbers badly. The two most common mistakes are single-digit errors (typing a 3 where there should be a 5) and adjacent transpositions, where you swap two neighboring digits and write 4512 instead of 4521. Both are invisible to the eye on a quick read.
The naive fix is server-side validation: submit the number, wait for a round trip, get an error back. That works, but it's wasteful. If the number is structurally wrong, you could have known that before the request left the client.
The smarter fix: encode a checksum directly into the number at the time it's issued. One digit is calculated from the others using a formula. Anyone with that formula can verify the number locally, instantly, with no server required.
The question is which formula, and how strict it needs to be.
Luhn: Fast, Simple, Good Enough
Hans Peter Luhn, an IBM engineer, developed this algorithm in 1954. The constraint was real: it had to be computable by hand or with simple mechanical devices. No computers. That constraint shaped everything about it.
The algorithm: Starting from the rightmost digit and moving left, double every second digit. If doubling produces a number greater than 9, subtract 9 from the result. Sum everything. If the total is divisible by 10, the number is valid.
Take the test card number 4111 1111 1111 1111:
Change any single digit and the sum breaks. That's the core guarantee.
What Luhn catches:
- Every single-digit substitution error
- Most adjacent transpositions
What it misses:
The transposition 09 ↔ 90 passes silently. At any adjacent pair of positions, one digit gets doubled and one doesn't. For 0 and 9: 0×2=0, 9×1=9 gives a sum of 9. Swap them: 9×2=18→9, 0×1=0 still gives 9. Same contribution either way. The checksum never sees it.
This is a known, documented limitation. For credit cards, it's an acceptable one. Luhn is the first gate, not the last. CVV checks, card network validation, and billing address verification all sit behind it. Luhn's job is to reject obvious garbage before it wastes a round trip.
Visa, Mastercard, American Express, Discover, and RuPay all use Luhn. So do IMEI numbers, the unique identifiers on mobile devices.
Verhoeff: No Blind Spots
Aadhaar is India's national biometric identity system, administered by UIDAI. More than 1.3 billion numbers have been issued, making it one of the largest identity systems ever deployed.
In 1969, Dutch mathematician Jacobus Verhoeff published his doctoral dissertation, Error Detecting Decimal Codes, with a specific goal: an algorithm with no exceptions.
He wanted to catch every single-digit error and every adjacent transposition, 09 ↔ 90 included. Verhoeff concluded that schemes like Luhn couldn't provide the guarantees he wanted, so he turned to a more sophisticated mathematical structure.
The algorithm uses three lookup tables:
A multiplication table built from the dihedral group D₅, the mathematical group describing the symmetries of a regular pentagon. It has 10 elements (5 rotations, 5 reflections), which maps cleanly onto the 10 decimal digits. This structure is what makes the transposition detection work without exceptions.
A permutation table that applies a different positional shuffle to each digit depending on where it sits in the number. This ensures that position matters; the same digit in a different position produces a different result.
An inverse table used to compute and verify the check digit.
You cannot run Verhoeff in your head. You need the tables. But the guarantees are strict:
- Every single-digit substitution is caught, without exception
- Every adjacent transposition is caught, including
09 ↔ 90
The 12th digit of every Aadhaar number is a Verhoeff check digit, derived from the first 11 using these tables.
Same Problem, Different Tradeoffs
Luhn is transparent. You can trace the arithmetic on paper and see exactly why a number fails. It has a known blind spot, but it lives inside a system with multiple subsequent validation layers, so that blind spot rarely matters in practice.
Verhoeff is opaque. There's no intuitive way to verify it mentally. The dihedral group math isn't something you trace by hand. But it closes every gap Luhn leaves open. For an identity system that prioritizes stronger error-detection guarantees, that matters.
The right algorithm isn't the mathematically superior one. It's the one whose failure modes are acceptable for what the number does.
Try It
Aadhaar validator (Verhoeff), running in your browser:
For Developers
If you're integrating a payment form, an identity verification flow, or any system that accepts a structured numeric identifier: validate on the client before the server call. A malformed number is catchable in microseconds with zero network cost. There's no reason to send it upstream.
The implementations above are ready to reference. Luhn is a handful of arithmetic operations and straightforward to port to any language. Verhoeff requires the three tables as constants, but the logic itself is a short loop.
Luhn and Verhoeff aren't the only algorithms in this family. Depending on what you're building, you may also encounter:
IBAN numbers use ISO 7064 MOD-97-10. The algorithm operates on alphanumeric strings, not just digits, and is the international standard for validating bank account numbers across Europe and beyond.
The Damm algorithm offers the same detection guarantees as Verhoeff (every single-digit error, every adjacent transposition) but uses only a single 10×10 lookup table instead of three. Published by H. Michael Damm in his thesis on totally anti-symmetric quasigroups.
The pattern across all of them is the same: one redundant digit, embedded at issuance, verified locally. Every system that issues identifiers at scale has solved this problem. The implementations are already written. There's no reason to skip the check.
What's Actually Going On
Both algorithms encode a contract into the number itself. One digit is redundant by design. Not information, but a commitment from the issuer to anyone who reads it: this number is internally consistent.
Luhn is more than 70 years old. Verhoeff more than 50. They predate the internet, the microprocessor, essentially every system they now run inside. The reason they've lasted is simple: the problem hasn't changed. Humans still transpose digits. Operators still make entry errors. The check digit is still the fastest, cheapest place to catch those errors before they propagate.
The next time you mistype a card number and get an instant error, no spinner, no server call, that's a 70-year-old algorithm working exactly as designed. Not the strongest option available. Just the right one for where it sits.
References:
- Verhoeff, J. (1969). Error Detecting Decimal Codes. Mathematical Centre Amsterdam.
- Luhn, H.P. US Patent 2,950,048. Filed 1954, granted 1960. Google Patents