Luhn is known under the phrase Luhn algorithm, Luhn formula, modulus 10 or mod 10 algrithm.
It is known as a simple checksum formula used for validating identification numbers, IMEI and credit card details. Furthermore it is used as NPI in the United States and multiple other countries.
It is developed by the IBM scientist Hans Peter Luhn and is described under the US PAtent 2.950.480 from August 1960.
The algorithm is in the public domain and is in wide use today. It is specified in ISO/IEC 7812-1. It is not intended to be a cryptographically secure hash function; it was designed to protect against accidental errors, not malicious attacks. Most credit cards and many government identification numbers use the algorithm as a simple method of distinguishing valid numbers from mistyped or otherwise incorrect numbers.
The formula verifies a credit card against its included check digit, which is usually appended to a partial credit card number to generate the full credit card number. This number must pass the following test:
- From the rightmost digit, which is the check digit, and moving left, double the value of every second digit. The check digit is not doubled, the first digit doubled is immediately to the left of the check digit. If the result of this doubling operation is greater than 9 (e.g., 8 × 2 = 16), then add the digits of the product (e.g., 16: 1 + 6 = 7, 18: 1 + 8 = 9) or, alternatively, the same result can be found by subtracting 9 from the product (e.g., 16: 16 − 9 = 7, 18: 18 − 9 = 9).
- Take the sum of all the digits.
- If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.
Assume an example of an credit card number “515621900409038” that will have a check digit added, making it of the form 515621900409038x:
|Credit Card number||5||1||5||6||2||1||9||0||0||4||0||9||0||3||8||4|
|Double every second||5||2||5||12||2||2||9||0||0||8||0||18||0||6||8||8|
The sum of all the digits in the third row is 67+x. In this case 205
The check digit (x) is obtained by computing the sum of the non-check digits then computing 9 times that value modulo 10 (in equation form, ((27 × 9) mod 10)). In algorithm form:
- Compute the sum of the non-check digits (27).
- Multiply by 9 (603).
- The units digit (3) is the check digit. Thus, x=3.
(Alternative method) The check digit (x) is obtained by computing the sum of the other digits (third row) then subtracting the units digit from 10 (67 => Units digit 7; 10 − 7 = check digit 3). In algorithm form:
- Compute the sum of the non-check digits (67).
- Take the units digit (7).
- Subtract the units digit from 10.
- The result (3) is the check digit. In case the sum of digits ends in 0 then 0 is the check digit.