Understanding the Luhn Algorithm
The Luhn algorithm, also known as the "modulus 10" or "mod 10" algorithm, is a simple checksum formula used to validate a variety of identification numbers, most notably credit card numbers. It was created by IBM scientist Hans Peter Luhn in 1954 and is now in the public domain. While not intended as a cryptographic hash, it does protect against accidental errors, such as a single mistyped digit or transposition of two adjacent digits.
How the Algorithm Works
- Start from the rightmost digit (the check digit) and move left.
- Double every second digit from the right (i.e., digits in even positions from the right).
- If doubling results in a value greater than 9, subtract 9 from the result (equivalent to summing the individual digits).
- Sum all the digits (both doubled and undoubled).
- If the total modulo 10 equals 0, the number is valid; otherwise, it is invalid.
Common Uses
Credit Card Numbers
Visa, Mastercard, American Express, and Discover all use Luhn validation.
IMEI Numbers
International Mobile Equipment Identity numbers used to identify cell phones.
Canadian Social Insurance
Canadian SIN numbers include a Luhn check digit for validation.
National Provider Identifier
US healthcare NPI numbers use the Luhn algorithm with a prefix.
Generating a Check Digit
To generate a check digit, apply the Luhn algorithm to the number with a zero appended. The check digit is the amount needed to bring the total to the next multiple of 10. Specifically: check digit = (10 - (sum mod 10)) mod 10.
Limitations
- Luhn cannot detect all transposition errors (e.g., swapping 09 and 90).
- It does not detect insertions or deletions of the digit 0.
- It is not a security measure and provides no protection against intentional manipulation.
- It only validates the format, not whether the number is actually issued or active.