Formulate of Luhn

In Mathematical and more precisely in Arithmetic modular, the formula of Luhn is used for its applications in Cryptologie. The algorithm of Luhn or the formula of Luhn , so known like the algorithm “module 10” or “MOD 10”, was developed in the years 1960 like a method of validation of identification of numbers. It is a simple formula of Vérification of nap (Checksum) used to validate a variety of account numbers, like the Credit card numbers the Canadian and insurance numbers social . Much of its notoriety comes from its adoption by the companies from credit cards quickly after its creation on the end of the year 1960 by Hans Peter Luhn (1896-1964), a scientist of IBM.

The algorithm belongs to the public domain and is largely widespread today. It was not conceived to be a protected Fonction of chopping cryptologiquement; it protects from the random errors, not against the malevolent attacks. The majority of the credit cards and much of governmental identification numbers use the algorithm like a simple method of distinction of valid numbers in random collections of figures.

Abstract explanations

The formula generates a figure of checking, which is generally attached to a partial account number to generate a complete account number. This account number (complete, i.e the number partial and the figure of checking) are subjected to the algorithm according to checking its correction:

one starts with the last figure (on the right) and one moves towards the left, by doubling the value of all the figures of even row: the last is treated in 1st, it is not doubled, the last but one (2nd) will be doubled. If the double of a figure exceeds 10, one replaces it by the sum of his figures. For example: 1111 become: 2121, while: 8763 becomes: 7733 (because 2×6=12, and 1+2=3; 2×8=16, and 1+6=7).
one adds together all the figures with the number thus obtained. For example, 1.111 becomes 2.121, then 2+1+2+1 what gives us 6; while 8.763 becomes 7.733, then 7+7+3+3 what gives us 20.
if the total is a multiple of 10, then the number is valid, being in agreement with the formula of Luhn, if not it is invalid. As follows: 1111 are not valid (as shown above, it leads to 6), while: 8763 is valid (as shown above, it leads to 20).

To determine the check digit added at the end of the number:

to calculate the sum as described above for a final check digit equal to 0,
if the sum is not a multiple of 10, to modify this figure to obtain a multiple of 10, is 10 - ( nap % 10) where nap % 10 indicates the remainder of the whole division of the sum calculated by 10.

Example:

Is the number 54321x to be calculated (X indicating the check digit to be calculated),
For X = 0, the checking of 543210 gives the sum 1 + 4 + 6 + 2 + 2 + 0 = 15 not multiple of 10,
One corrects the figure X = 10 - (15% 10) = 10 - 5 = 5
For X = 5, the checking of 543215 gives the sum 1 + 4 + 6 + 2 + 2 + 5 = 20 multiple of 10.

Algorithm

The algorithm proceeds in three stages.

the algorithm multiplies by two a figure out of two, while starting with before the last and while moving from right to left. If a figure which is multiplied by two is larger than nine (as it is the case for example for 8 which becomes 16), then it should be brought back to a figure between 1 and 9. For that, there are 2 manners of making (for an identical result):
1. Is the figures composing the doubling are added (for figure 8: one obtains initially 16 by multiplying it by 2 then 7 by summoning the figures composing the result: 1+6).
2. Is one withdraws to him 9 (for figure 8: one obtains 16 by multiplying it by 2 then 7 by withdrawing 9 from the result).
the sum of all the figures obtained is carried out.
the result is divided by 10. If the remainder of division is equal to zero, then the original number is valid.

function checkLuhn ( string purportedCC): boolean { int sum := 0 int nDigits := length ( purportedCC ) int parity := nDigits AND 1 for I from nDigits-1 to 0 { int digit: = integer (purportedCC) yew (I AND 1) = parity digit: = digit × 2 yew digit > 9 digit: = digit - 9 sum : = sum + digit } return ( sum % 10) = 0 }

Example

Let us consider the identification of the number 456-565-654. The first stage consists in doubling a figure on two on the basis of the second until the end, and to make the sum of all the figures, doubled or not. The following table shows this stage (the coloured lines indicate the doubled figures):

The sum, equalizes to 30, is divided by 10: the remainder is 0, therefore the number is valid.

External bonds

C# Implementation (English)
Implementation Java (English)
Implementation Python (English)
C++ Implementation (French)
C# Implementation (French)

Random links: