The formula verifies a number against its included check digit, which is usually appended to a partial account number to generate the full account number. This number must pass the following test:
From the rightmost digit and moving left, double the value of every second digit. The check digit is neither doubled nor included in this calculation; the first digit doubled is the digit located immediately left of the check digit. If the result of this doubling operation is greater than 9, then add the digits of the result or, alternatively, the same final result can be found by subtracting 9 from that result.
If the total modulo 10 is equal to 0 then the number is valid according to the Luhn formula; otherwise it is not valid.
Assume an example of an account number "7992739871" that will have a check digit added, making it of the form 7992739871x:
Account number
7
9
9
2
7
3
9
8
7
1
x
Double every other
7
18
9
4
7
6
9
16
7
2
x
Sum digits
7
9
9
4
7
6
9
7
7
2
x
-
The sum of all the digits in the third row, the sum of the sum digits, is 67. The check digit is obtained by computing the sum of the sum digits then computing 9 times that value modulo 10 ). In algorithm form:
Compute the sum of the sum digits.
Multiply by 9.
603 mod 10 is then 3, which is the check digit. Thus, x=3.
The check digit is obtained by computing the sum of the other digits then subtracting the units digit from 10. In algorithm form:
Compute the sum of the sum digits.
Take the units digit.
Subtract the units digit from 10.
The result is the check digit. In case the sum of digits ends in 0 then 0 is the check digit.
This makes the full account number read 79927398713. Each of the numbers 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 can be validated as follows.
Double every second digit, from the rightmost: = 2, = 16, = 6, = 4, = 18
Sum all the individual digits : x + + 7 + + 9 + + 7 + + 9 + + 7 = x + 67.
If the sum is a multiple of 10, the account number is possibly valid. Note that 3 is the only valid digit that produces a sum that is a multiple of 10.
Thus these account numbers are all invalid except possibly 79927398713 which has the correct check digit.
Alternately, you can use the same checksum creation algorithm, ignoring the checksum already in place as if it had not yet been calculated. Then calculate the checksum and compare this calculated checksum to the original checksum included with the credit card number. If the included checksum matches the calculated checksum, then the number is valid.
Strengths and weaknesses
The Luhn algorithm will detect any single-digit error, as well as almost all transpositions of adjacent digits. It will not, however, detect transposition of the two-digit sequence 09 to 90. It will detect most of the possible twin errors. Other, more complex check-digit algorithms can detect more transcription errors. The Luhn mod N algorithm is an extension that supports non-numerical strings. Because the algorithm operates on the digits in a right-to-left manner and zero digits affect the result only if they cause shift in position, zero-padding the beginning of a string of numbers does not affect the calculation. Therefore, systems that pad to a specific number of digits can perform Luhn validation before or after the padding and achieve the same result. Prepending a 0 to odd-length numbers makes it possible to process the number from left to right rather than right to left, doubling the odd-place digits. The algorithm appeared in a United States Patent for a hand-held, mechanical device for computing the checksum. Therefore, it was required to be rather simple. The device took the mod 10 sum by mechanical means. The substitution digits, that is, the results of the double and reduce procedure, were not produced mechanically. Rather, the digits were marked in their permuted order on the body of the machine.
Pseudocode implementation
function checkLuhn
Where used
In addition to credit card numbers, this algorithm is also used to calculate the check digit on SIM card numbers. For example. Take the SIM Serial number 89610195012344000018 The number printed on the SIM card is usually a subset of this. The last two digits are check digits. checkLuhn will return 1 - the first check digit checkLuhn will return 8 - the second check digit. This shortened number, followed by its check digit is printed on the SIM card itself.
