Luhn algorithm

The Luhn algorithm was developed in the 1960s as a method of validating identification numbers. The algorithm is in the public domain and is in wide use today. It is not intended to be cryptographically secure hash; it protects against random error, not malicious attack.

Most credit cards and many government identification numbers use the algorithm as a simple method of distinguishing valid numbers from collections of random digits.

Algorithm

The algorithm proceeds in three steps. Firstly, every second digit, beginning with the next-to-rightmost and proceeding to the left, is doubled. If that result is greater than nine, its digits are summed. Thus, a 2 becomes 4 and a 7 becomes 5. Secondly, all the digits are summed. Finally, the result is divided by 10. If the remainder is zero, the original number is valid.

Example

Consider the example identification number 456-565-654.

Step One: Double every other digit, sum that result's digits

4  5  6  5  6  5  6  5  4

|  |  |  |  |  |  |  |  |
V  V  V  V  V  V  V  V  V

4 10  6 10  6 10  6 10  4

|  |  |  |  |  |  |  |  |
V  V  V  V  V  V  V  V  V

4  1  6  1  6  1  6  1  4

Step Two: Sum the resulting digits

4+1+6+1+6+1+6+1+4 = 30

Step Three: Divide by 10, note remainder

30 modulo 10 is zero.

If the remainder is zero, the number is valid.