The Luhn formula is a simple checksum formula that is used in the validation of various identification numbers such as credit card numbers, social security numbers, IMEI numbers and many others. The algorithm validates the number against an included check digit in the number itself, usually the last digit. The Luhn formula is now in the public domain and is widely used in various industries and specified in ISO/IEC 7812-1.
The Luhn formula is also known as the Luhn algorithm, modulus 10 algorithm or mod 10 algorithm.
The Luhn Formula was devised by Hans Peter Luhn, an IBM scientist, who filed a patent for the formula in 1954, which was granted in 1960. The formula was not designed to be a cryptographically secure hash function, but rather as a simple way to protect against accidental errors in creating unique identification numbers. Many government agencies and private institutions used the formula for distinguishing valid numbers from mistyped, incorrect or simply fraudulent numbers.
The formula is used to verify a series of numbers by checking that an included check digit is correct. This check digit is usually attached to partial number in order to complete it.
The following process is the generation of the check digit:
- Starting from the rightmost digit, double the value of every second digit.
- If the resulting product from the first step is above 9, add the two digits (e.g., 5 × 3 = 15, 1 + 5 = 6). If the result is 9 or less, retain the number.
- Take the sum of all the digits.
- Multiply the sum by 9 and take the "modulo 10" of the sum; the result is the check digit.
Example: Number series 927638965
|
9
|
2
|
7
|
6
|
3
|
8
|
9
|
6
|
5 is the check digit
|
|
9
|
4
|
7
|
12
|
3
|
16
|
9
|
12
|
|
|
9
|
4
|
7
|
3
|
3
|
7
|
9
|
3
|
sum = 45; 45 × 9 = 405 (mod 10) = 5
|
In order to check that the number is valid, simply follow the algorithm excluding the check digit, and if the same result is obtained as the check digit, then the number is valid according to the Luhn formula. However, this algorithm is not very reliable and is only able to detect mostly single-digit errors and transpositions of adjacent numbers, except the transposition of the two-digit sequence 09 to 90. More complicated algorithms like the Verhoeff algorithm and Damm algorithm are able to detect more transcription errors.
