|
|
|
|
|
|
|
|
LUHN Algorithm |
|
|
Informal
explanation
The formula
generates a check
digit, which is
usually appended to
a partial account
number to generate
the full account
number. This account
number must pass the
following algorithm
(and the check digit
chosen and placed so
that the full
account number
will):
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. For
example, 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).
In the two examples
above, if a check
digit was to be
added to the front
of these numbers,
then 4 might be
added to 1111 to
make 41111 (ie 4+
2+1+2+1 =10), while
0 would be added to
8763 to make 08763
(0+ 7+7+3+3 = 20).
It is usually the
case that check
digits are added to
the end, although
this requires a
simple modification
to the algorithm to
determine an ending
check digit given
the rest of the
account number.
A weakness in this
algorithm is that it
can be bypassed by
using all zero
digits as the
number. |
|
|
Algorithm
The algorithm
proceeds in three
steps. First, 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
(which is
equivalent, for any
number in the range
10 though 18, of
subtracting 9 from
it). Thus a 2
becomes 4 and a 7
becomes 5. Second,
all the digits are
summed. Third, the
result is divided by
10. If the remainder
is zero, the
original number is
valid. |
|
|
function
checkLuhn(string
purportedCC) {
int sum := 0
int nDigits := length(purportedCC)
int parity := nDigits modulus 2
for i from 0 to nDigits - 1 {
int digit :=
integer(purportedCC[i])
if i modulus 2 = parity
digit
:= digit × 2
if digit > 9
digit
:= digit - 9
sum := sum +
digit
}
return (sum modulus 10) = 0
} |
|
|
|
Example |
Consider the example
identification
number 446-667-651.
The first step is to
double every other
digit, starting with
the second-to-last
digit and moving
left, and sum the
digits in the
result. The
following table
shows this step
(highlighted rows
indicating doubled
digits):
|
|
Digit |
Double |
Reduce |
Sum of
digits |
|
1 |
|
1 |
1 |
|
5 |
10 |
1+0 |
1 |
|
6 |
|
6 |
6 |
|
7 |
14 |
1+4 |
5 |
|
6 |
|
6 |
6 |
|
6 |
12 |
1+2 |
3 |
|
6 |
|
6 |
6 |
|
4 |
8 |
0+8 |
8 |
|
4 |
|
4 |
4 |
|
Total Sum: |
40 |
|
|
|
|
The sum of 40 is
divided by 10; the
remainder is 0, so
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 (or vice
versa). Other, more
complex check digit
algorithms (such as
the Verhoeff
algorithm) can
detect more
transcription
errors. |
|
|
|
|
|
|
|