The Luhn algorithm was created by Hans Peter Luhn and is a way of creating a simple checksum for a number. This algorithm, also known as the mod 10 algorithm, is used in a wide variety of applications but is commonly associated with credit card numbers.

If you look at the numbers on the front of your credit card the last digit on the right is the checksum. An algorithm is done on the other numbers and if the checksum is the same then the number is considered valid.

Outside of credit card numbers, the Luhn algorithm can be used to create a checksum on any number that you want to store. It is especially handy when you want to give users a number that they will be hand typing into a computer. The checksum helps spot any errors in typing in the number before that number is processed. The good thing about the Luhn algorithm is that it doesn't matter how long the number is so it will work with any kind of digit sequence.

## The Luhn Algorithm

The Luhn algorithm works using the following steps.

- Working backwards from the right side of the number (excluding the check digit if it is present) take every other number and multiply it by 2.
- If the number exceeds 9 (i.e. it has double digits) then add the two numbers together. Alternatively you can also take away 9 which does the same thing.
- Add everything together.
- Multiply by 9.
- Take the modulus of the sum of the number and 10. The number left over is the checksum. An alternative approach is to just find the last character of this final number, which has the same value.

Let's look at this algorithm with a real example. The following number is a test credit card number used on a popular payment service.

`378282246310005`

Because we know that the checksum exists in the number (the 5 on the end) we first we remove the checksum value and reverse the number.

`00013642282873`

Then we separate the number out into odd and even values.

```
3 7 8 2 8 2 2 4 6 3 1 0 0 0
Odd: 0 1 6 2 8 8 3
Even: 0 0 3 4 2 2 7
```

We then run through the even numbers and multiply each by 2, also subtracting any numbers that are over 9.

```
0x2 = 0
0x2 = 0
3x2 = 6
4x2 = 8
2x2 = 4
2x2 = 4
7x2 = 14 - 9 = 5
```

Now we add all of the numbers together.

`0 + 0 + 0 + 1 + 6 + 6 + 8 + 2 + 4 + 8 + 4 + 8 + 5 + 3 = 55`

Another way of looking at this step would be by adding the odd and even number together separately. This still gives the same results but shows that we aren't changing the odd numbers at all in this process. Some implementations of the algorithm do this so it's something to watch out for.

```
Odd: 0 + 1 + 6 + 2 + 8 + 8 + 3 = 28
Even: 0 + 0 + 6 + 8 + 4 + 4 + 5 = 27
28 + 27 = 55
```

The penultimate step is to multiply the value by 9.

`55 x 9 = 495`

Finally, we can do the modulus against 10 to see the remainder.

`495 % 10 = 5`

The final result here is "5", which matches the original checksum we removed from the number. This means that the checksum is correct and the number is valid.

One thing to note that isn't mentioned in some articles online is that there is a slight difference if the number has an odd number of characters. If the number has an odd number of characters then we just reverse the odd and even numbers and perform the calculation slightly differently. Here is the same number as before, but with a single character (0 in this case) taken off of the end to make it an odd number of characters.

```
3782822463100
Reverse: 0 0 1 3 6 4 2 2 8 2 8 7 3
'Even' numbers: 0 1 6 2 8 8 3
Multiply by 2:
0 x 2 = 0
1 x 2 = 2
6 x 2 = 12 - 9 = 3
2 x 2 = 4
8 x 2 = 16 - 9 = 7
8 x 2 = 16 - 9 = 7
3 x 2 = 6
Add all resulting number together:
0 + 0 + 2 + 3 + 3 + 4 + 4 + 2 + 7 + 2 + 7 + 7 + 6 = 47
Multiply by 9:
47 x 9= 423
Modulus 10:
423 % 10 = 3
```

As you can see the checksum we get back here is 3. Different from the previous value of 5.

## Writing PHP Code

The PHP code to generate a Luhn number is pretty straight forward. All we need to do is convert the value we are given to a string so we can iterate through it using the built in array like syntax. In PHP we can reference each character in the string like we would an array.

`$char = $value[1];`

To extract all of the characters in a string we just need to wrap this code in a loop. Also, because we deal with Luhn numbers backwards, looping through the values from right to left is simply a case of counting backwards in the loop.

The only other thing of note is the $parity variable. This is used to offset the Luhn odd/even calculation so that we are able to deal with odd and even lengths of values in the same way.

```
function generateChecksum($value) {
if (!is_numeric($value)) {
throw new \InvalidArgumentException(__FUNCTION__ . ' can only accept numeric values.');
}
// Force the value to be a string so we can work with it like a string.
$value = (string) $value;
// Set some initial values up.
$length = strlen($value);
$parity = $length % 2;
$sum = 0;
for ($i = $length - 1; $i >= 0; --$i) {
// Extract a character from the value.
$char = $value[$i];
if ($i % 2 != $parity) {
$char *= 2;
if ($char > 9) {
$char -= 9;
}
}
// Add the character to the sum of characters.
$sum += $char;
}
// Return the value of the sum multiplied by 9 and then modulus 10.
return ($sum * 9) % 10;
}
```

To calculate the checksum of a value we just pass in the value and store the result.

```
$checksum = generateChecksum('1234567890'); // returns 3.
```

This checksum can be printed out with the number passed in so that the user will see the value "12345678903". This means that if the user is asked to type in the number then we can use the checksum to make sure that the number is correct.

## An Alternative Implementation

An alternative approach is to use a look up table so that we aren't multiplying numbers or detecting if the value is over 9. This means we just need to work out what every between 0 and 9 will produce when we multiply it by 2 and subtract 9 if the value is over 9. This gives us the following set of numbers.

```
0 = 0
1 = 2
2 = 4
3 = 6
4 = 8
5 = 1
6 = 3
7 = 5
8 = 7
9 = 9
```

All we need to do is load these numbers into an array and we can easily get the calculated value for that number without actually doing the calculation. As we also need to flip between odd and even numbers we need two tables, one for the static numbers and one for the calculated numbers.

```
function generateChecksum1($value) {
if (!is_numeric($value)) {
throw new \InvalidArgumentException(__FUNCTION__ . ' can only accept numeric values.');
}
// Force the value to be a string so we can work with it like a string.
$value = (string) $value;
// Set some initial values up.
$length = strlen($value);
$sum = 0;
$flip = 1;
$sumTable = [
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[0, 2, 4, 6, 8, 1, 3, 5, 7, 9],
];
for ($i = $length - 1; $i >= 0; --$i) {
// Map each character against a map of values.
$sum += $sumTable[$flip++ % 2][$value[$i]];
}
// Multiply everything by 9.
$sum *= 9;
// Last digit of the new value is check digit.
return substr($sum, -1, 1);
}
```

The above code also makes use of PHP loose typing by allowing us to simply return the last character of the sum instead of returning the result of modulus 10.

## Validation

Of course, once we have the Luhn number in hand we need to have a mechanism of validating that value. This is just a case of extracting the original value and the checksum, recalculating the checksum using the function above, and then comparing the original checksum with the one we calculated ourselves.

```
$value = '12345678903';
// Extract the checksum.
$extractedChecksum = substr($value, -1);
// Extract the value.
$extractedValue = substr($value, 0, -1);
// Calculate the checksum on the extracted value.
$calcuatedChecksum = $luhn->generateChecksum($extractedValue);
// Compare!
if ($extractedChecksum == $calcuatedChecksum) {
echo 'Number is valid';
}
```

The above code will print out "Number is valid" as the checksum we calculated is the same as the checksum we extracted from the original number. If we change the input number to something else, 42345678903 for example, then it will not validate correctly.

## Common Problems

Whilst the Luhn algorithm is a neat way to validate values, it does have a couple of weaknesses. It will detect any single digit errors as well as almost all transpositions of adjacent digits. It is not able to detect certain transpositions though, so if your user enters "09" when they meant "90" the algorithm will not notice this. The numbers 99099 and 99909 are clearly different, but they both produce the checksum of 4.

You can be pretty sure that the number entered is correct, there is a very small chance that the number is wrong. This means you still need to have upstream validation and error detection as you can't 100% guarantee that the number is correct.

The most common problem you need to think about when using numbers with Luhn checksums is how to store and retrieve them. You really want to avoid the double checksum problem where you add a checksum to a number that already has a checksum. Conversely, there is the issue of validating a number that doesn't have the checksum in place as the validation will not return the correct result.

The best way I have found of tackling this is by following two simple rules.

- Always store your number with the checksum.
- Always print your number out to the user with the checksum.

This means that when your number is going into the database you should be absolutely sure that it contains a checksum before being saved. This allows you to treat all numbers in your database in the same way.

When printing out the numbers for your users you just need to print them out. There is no need to ensure that the checksum is in place before hand.

I have seen implementations where the number is saved without the checksum and although this worked it did catch the developers out a couple of times as there is this disconnect between the value in the database and the value being presented to the user. This approach can also lead to the double encoding problem if you don't remember to always send your number to the front end with the checksum intact.

The Luhn algorithm will catch most validation issues before the number reaches critical systems. Adding it to form validation will absolutely help your users enter the correct numbers. You can use it with credit card numbers (since they already have that in place) but you can apply the same rules to discount codes, referral codes, or anything that the user might copy and paste from one place to another.