Monday, May 08, 2006
The Luhn algorithm
A method of validating identification numbers. It is a simple
checksum formula used to validate account numbers,
such as credit card numbers and Canadian Social
it protects against accidental error, not malicious attack.
Starting with the second to last digit and moving left,
double the value of all the alternating digits.
For any digits that thus become 10 or more,
add their digits together.
1111 becomes 2121, while 8763 becomes 7733
(from 2x8=16 -> 1+6=7 and 2x6=12 -> 1+2=3).
Add all these digits together.
For example, 1111 becomes 2121,
then 2+1+2+1 is 6; while 8763 becomes 7733, then 7+7+3+3 is 20.
If the total ends in 0 (put another way, if the total modulus 10 is congruent to 0),
then the number is valid according to the Luhn formula,
else it is not valid.
So, 1111 is not valid (as shown above, it comes out to 6),
while 8763 is valid (as shown above, it comes out to 20).