Luhn algorithm
The Luhn algorithm or the Luhn formula , also known as the “ Modulo 10” or “mod 10” algorithm and as the double-add-double method, is a simple method for calculating a checksum . It was developed in the 1950s by the German-American computer scientist Hans Peter Luhn and is now in the public domain and very widespread. Among other things, the Luhn algorithm is used to verify credit card numbers and Canadian social security numbers , ISINs and the seven-digit account numbers of Deutsche Bank and Commerzbank as well as many savings banks . It is also used for the numbers of the locomotives and railcars according to the UIC labeling scheme , as has been the case for the Bundesbahn series scheme since 1968 .
The Luhn algorithm recognizes every error in individual digits, as well as interchanges of neighboring digits.
Informal explanation
The Luhn algorithm generates a check digit , which is usually added to the end of the incomplete identification number. This gives the complete number. This is considered valid if it passes the following checking algorithm:
- Go through the number digit by digit from right to left and form the sum of the digits, but: Double every second digit and if the result is a value greater than 9, subtract 9
- If the total has a 0 as the last digit, recognize the number as valid and not otherwise
For example, to check the number 18937, the digits are run through from right to left, i.e. starting with 7, and added up. Every second digit is doubled, i.e. in this example the 3 and the 8. Since doubling the 8 results in a value greater than 9, 9 is subtracted from this, so that 16 - 9 = 7.
So the sum is calculated as 7 + (2 × 3) + 9 + (2 × 8 - 9) + 1 = 7 + 6 + 9 + 7 + 1 = 30. Since the 30 ends in 0, the number is valid.
Technically, a kind of cross-sum of the number is calculated, with special treatment for every second digit. The result is reduced modulo 10; This means that it does not depend on the result itself, but only on the remainder that comes out when dividing by 10 as an integer. This remainder is equal to the last digit of the result.
If this remainder is 0, which means that the result is divisible by 10, the number is considered valid, otherwise not.
The Luhn algorithm recognizes it if a number is entered incorrectly when entering a number. This changes the total by an amount between 1 and 9 and is therefore no longer divisible by 10. If 4 is entered instead of 1 in the above example, the result is 33 and therefore not divisible by 10. If 6 is entered instead of 8, the result is 26 and therefore not divisible by 10.
A single incorrect number entry would also be recognized with a normal checksum - but not one of the frequently occurring " number rotations ", i.e. the interchanging of two consecutive numbers. This would not change the normal checksum.
The Luhn algorithm recognizes such a number rotator by the fact that a different digit is now doubled than before and the checksum changes. For example, the number 190 is valid (checksum 10) but 910 is not (checksum 11); H. the number rotated 19 to 91 is recognized. The only exceptions are the rotated numbers of the digits 0 and 9, as their checksums with and without doubling are the same. For example, 190 and 109 are both valid (checksum 10); H. the number rotated 90 to 09 is not recognized.
Interchanges of digits whose positions differ by an even amount are not recognized - for example, if the 3rd and 5th digits or the 2nd and 6th digits are swapped. Likewise, it may not be recognized if two or more digits are entered incorrectly.
Example implementations
In the following implementations of the algorithm, the number is passed numberto the function as a character sequence, i.e. as a string checkLuhn. In the function, this string is run through naturally from left to right - that is, the other way around as in the definition of the algorithm. However, by initially determining whether the length of the string is even or odd, it is still possible to double the digits in the correct positions.
Pseudo code
function checkLuhn(string number)
{
int sum := 0
int lng := length(number)
int parity := lng modulo 2
for i from 0 to lng - 1
{
int digit := toInteger(number[i])
if i modulo 2 = parity
{
digit := digit × 2
if digit > 9
digit := digit - 9
}
sum := sum + digit
}
return (sum modulo 10) = 0
}
Java
public static boolean check(int[] digits)
{
int sum = 0;
int length = digits.length;
for (int i = 0; i < length; i++)
{
// get digits in reverse order
int digit = digits[length - i - 1];
// every 2nd number multiply with 2
if (i % 2 == 1)
digit *= 2;
sum += digit > 9 ? digit - 9 : digit;
}
return sum % 10 == 0;
}
python
def checkLuhn(number):
sum = 0
parity = len(number) % 2
for i, digit in enumerate(int(x) for x in number):
if i % 2 == parity:
digit *= 2
if digit > 9:
digit -= 9
sum += digit
return sum % 10 == 0
Or other version:
def checkLuhn(number):
return sum(map(int, number)[1 - len(number) % 2::2] + map(lambda x: x * 2 - 9 if x * 2 > 9 else x * 2, map(int, number)[len(number) % 2::2])) % 10 == 0
example
Consider the example identification number 446-667-651.
| Digit | Doubled | Reduced | Sum of the digits |
|---|---|---|---|
| 1 | 1 | 1 | |
| 5 | 10 | 10 - 9 | 1 |
| 6th | 6th | 6th | |
| 7th | 14th | 14 - 9 | 5 |
| 6th | 6th | 6th | |
| 6th | 12 | 12 - 9 | 3 |
| 6th | 6th | 6th | |
| 4th | 8th | 8th | 8th |
| 4th | 4th | 4th | |
| Total: | 40 | ||
The sum 40 is divided by an integer by 10; the rest is 0 - so the number is valid.
Use with EC cards
With EC cards, the calculation of the number differs slightly. This is because every second number is doubled, starting from the rightmost number (instead of the second from the right).
Individual evidence
- ↑ US Patent No. 2,950,048 , filed January 6, 1954, patent issued August 23, 1960.