Theory

Luhn Check Digit Routine

The basis of calculation of the check digit is the Luhn check digit routine. This provides a weighting for each of the credit card digits and subsequently requires a number of operations to be performed as described below.

Let us use the MasterCard format for this exercise. The first 15 decimal characters are weighted 212121212121212 by multiplying each digit by its weight. If the result of any of the multiplications is a 2-digit number, the digits are added to produce a single decimal number.

Example:

16-digit card number with X as the unknown check digit: 

        5 3 2 1   0 0 4 6   7 3 2 2   9 8 1 X		  number
        2 1 2 1   2 1 2 1   2 1 2 1   2 1 2		x weight
       10 3 4 1   0 0 8 6  14 3 4 2  18 8 2 

        1+3+4+1 + 0+0+8+6 + 5+3+4+2 + 9+8+2 = 56
        
       next highest multiple of 10 is 60


       so                           60 - 56 = 4

Procedure

  1. multiply each character by its weight, and add the digits if more than 10.
  2. total all 15 results
    In the example the result is 56
  3. Subtract this from the next highest multiple of 10
This is the checksum digit.

An helpful circuit for doing these calculations is the BCD Adder.