Generating Luhn Checksums

Question

There are lots of implementations for validating Luhn checksums but very few for generating them. I've come across this one however in my tests it has revealed to be buggy and I don't understand the logic behind the delta variable.

I've made this function that supposedly should generated Luhn checksums but for some reason that I haven't yet understood the generated checksums are invalid half of the time.

function Luhn($number, $iterations = 1)
{
    while ($iterations-- >= 1)
    {
        $stack = 0;
        $parity = strlen($number) % 2;
        $number = str_split($number, 1);

        foreach ($number as $key => $value)
        {
            if ($key % 2 == $parity)
            {
                $value *= 2;

                if ($value > 9)
                {
                    $value -= 9;
                }
            }

            $stack += $value;
        }

        $stack = 10 - $stack % 10;

        if ($stack == 10)
        {
            $stack = 0;
        }

        $number[] = $stack;
    }

    return implode('', $number);
}

Some examples:

Luhn(3); // 37, invalid
Luhn(37); // 372, valid
Luhn(372); // 3728, invalid
Luhn(3728); // 37283, valid
Luhn(37283); // 372837, invalid
Luhn(372837); // 3728375, valid

I'm validating the generated checksums against this page, what am I doing wrong here?

---

For future reference, here is the working function.

function Luhn($number, $iterations = 1)
{
    while ($iterations-- >= 1)
    {
        $stack = 0;
        $number = str_split(strrev($number), 1);

        foreach ($number as $key => $value)
        {
            if ($key % 2 == 0)
            {
                $value = array_sum(str_split($value * 2, 1));
            }

            $stack += $value;
        }

        $stack %= 10;

        if ($stack != 0)
        {
            $stack -= 10;
        }

        $number = implode('', array_reverse($number)) . abs($stack);
    }

    return $number;
}

I dropped the $parity variable since we don't need it for this purpose, and to verify:

function Luhn_Verify($number, $iterations = 1)
{
    $result = substr($number, 0, - $iterations);

    if (Luhn($result, $iterations) == $number)
    {
        return $result;
    }

    return false;
}

Onlybegotten

By the way, verifying a checksum is identical to generating it and checking if it's zero - so all those 'verify' routines can also be used to generate. – Ketene

@Nick: Yeah, but that involves checking 10 different digits, I prefer the other way around (verify using the generate function). – Onlybegotten

What? No, you just 'verify' the number with 0 appended, then replace the last digit with (9-result). – Ketene

Sorry, you're right I misunderstood your statement. – Onlybegotten

I've only found your implementation of Luhn generation codes in PHP as a usable one so far. I think it would be interesting if you create a simple repository in github with it. What do you think? – Banderole

@GmonC: Thanks, but why would a GitHub repository be more useful than this question? – Onlybegotten

@Alix Axel: it's a repository. If people would like to improve it (or even yourself), they don't need to comment here like I did, they can just fork it. Github IMO it's better organized for code that are more generalized (like this one) than other snippets of code around here. I said github because it's really easy to setup an account. – Banderole

@GmonC: The thing is Git used to be a pain in the ass to setup under Windows, I'll see what I can do about that. – Onlybegotten

@Alix Axel: You can try Bitbucket, and use TortoiseHg (Bitbucket uses mercurial). I use it in my Windows 7 workstation and it works perfectly. (Mercurial in cmd works as well) – Banderole

Answer 1

Edit: Sorry, I realize now that you had almost my entire answer already, you had just incorrectly determined which factor to use for which digit.

My entire answer now can be summed up with this single sentence:

You have the factor reversed, you're multiplying the wrong digits by 2 depending on the length of the number.

---

Take a look at the Wikipedia article on the Luhn algorithm.

The reason your checksum is invalid half the time is that with your checks, half the time your number has an odd number of digits, and then you double the wrong digit.

For 37283, when counting from the right, you get this sequence of numbers:

  3 * 1 =  3             3
  8 * 2 = 16 --> 1 + 6 = 7
  2 * 1 =  2             2
  7 * 2 = 14 --> 1 + 4 = 5
+ 3 * 1 =  3             3
=                       20

The algorithm requires you to sum the individual digits from the original number, and the individual digits of the product of those "every two digits from the right".

So from the right, you sum 3 + (1 + 6) + 2 + (1 + 4) + 3, which gives you 20.

If the number you end up with ends with a zero, which 20 does, the number is valid.

Now, your question hints at you wanting to know how to generate the checksum, well, that's easy, do the following:

1. Tack on an extra zero, so your number goes from xyxyxyxy to xyxyxyxy0
2. Calculate the luhn checksum sum for the new number
3. Take the sum, modulus 10, so you get a single digit from 0 to 10
4. If the digit is 0, then congratulations, your checksum digit was a zero
5. Otherwise, calculate 10-digit to get what you need for the last digit, instead of that zero

Example: Number is 12345

1. Tack on a zero: 123450

2. Calculate the luhn checksum for 123450, which results in

   0   5    4    3    2    1
   1   2    1    2    1    2  <-- factor
   0   10   4    6    2    2  <-- product
   0  1 0   4    6    2    2  <-- sum these to: 0+1+0+4+6+2+2=15
   

3. Take the sum (15), modulus 10, which gives you 5

4. Digit (5), is not zero
5. Calculate 10-5, which gives you 5, the last digit should be 5.

So the result is 123455.

Ocean

Thanks, I realized that my rightmost pair digit in this case is always my last digit (since I'm generating the checksum digit). – Onlybegotten

Answer 2

your php is buggy, it leads into an infinite loop. This is the working version that I'm using, modified from your code

function Luhn($number) {

$stack = 0;
$number = str_split(strrev($number));

foreach ($number as $key => $value)
{
    if ($key % 2 == 0)
    {
        $value = array_sum(str_split($value * 2));
    }
    $stack += $value;
}
$stack %= 10;

if ($stack != 0)
{
    $stack -= 10;     $stack = abs($stack);
}


$number = implode('', array_reverse($number));
$number = $number . strval($stack);

return $number; 

}

Create a php and run in your localhost Luhn(xxxxxxxx) to confirm.

Ludivinaludlew

Answer 3

BAD

I literally cannot believe how many crummy implementations there are out there.

IDAutomation has a .NET assembly with a MOD10() function to create but it just doesn't seem to work. In Reflector the code is way too long for what it's supposed to be doing anyway.

---

BAD

This mess of a page which is actually currently linked to from Wikipedia(!) for Javascript has several verification implementations that don't even return the same value when I call each one.

---

GOOD

The page linked to from Wikipedia's Luhn page has a Javascript encoder which seems to work :

// Javascript
String.prototype.luhnGet = function()
{
    var luhnArr = [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8,1,3,5,7,9]], sum = 0;
    this.replace(/\D+/g,"").replace(/[\d]/g, function(c, p, o){
        sum += luhnArr[ (o.length-p)&1 ][ parseInt(c,10) ]
    });
    return this + ((10 - sum%10)%10);
};

alert("54511187504546384725".luhnGet());​

---

GOOD

This very useful EE4253 page verifies the check-digit and also shows the full calculation and explanation.

---

GOOD

I needed C# code and ended up using this code project code:

// C#
public static int GetMod10Digit(string data)
        {
            int sum = 0;
            bool odd = true;
            for (int i = data.Length - 1; i >= 0; i--)
            {
                if (odd == true)
                {
                    int tSum = Convert.ToInt32(data[i].ToString()) * 2;
                    if (tSum >= 10)
                    {
                        string tData = tSum.ToString();
                        tSum = Convert.ToInt32(tData[0].ToString()) + Convert.ToInt32(tData[1].ToString());
                    }
                    sum += tSum;
                }
                else
                    sum += Convert.ToInt32(data[i].ToString());
                odd = !odd;
            }

            int result = (((sum / 10) + 1) * 10) - sum;
            return result % 10;
        }

---

GOOD

This validation code in C# seems to work, if a little unwieldy. I just used it to check the above was correct.

Hummocky

I actually ended up spending way too much time trying to find working code and should have just written it myself. Remember that a validation algorithm and a checking algorithm are basically the same - with validation you just create the checksum for n-1 digits in the string and compare with last digit – Hummocky

Your c# answer does not return the correct result when sum % 10 == 0, also the "validation code in c#" link is dead. – Porcupine

Answer 4

This is a function that could help you, it's short and it works just fine.

function isLuhnValid($number)
{
    if (empty($number))
        return false;

    $_j = 0;
    $_base = str_split($number);
    $_sum = array_pop($_base);
    while (($_actual = array_pop($_base)) !== null) {
        if ($_j % 2 == 0) {
            $_actual *= 2;
            if ($_actual > 9)
                $_actual -= 9;
        }
        $_j++;
        $_sum += $_actual;
    }
    return $_sum % 10 === 0;
}

Jefferey

Answer 5

There's now a github repo based on the original question/answer. See

https://github.com/xi-project/xi-algorithm

It's also available at packagist

Gerrigerrie

Answer 6

Since the other answers that displayed or linked to C# weren't working, I've added a tested and more explanatory C# version:

    /// <summary>
    /// Calculates Luhn Check Digit based on 
    /// https://en.wikipedia.org/wiki/Luhn_algorithm
    /// </summary>
    /// <param name="digits">The digits EXCLUDING the check digit on the end. 
    /// The check digit should be compared against the result of this method.      
    /// </param>
    /// <returns>The correct checkDigit</returns>
    public static int CalculateLuhnCheckDigit(int[] digits)
    {
        int sum = 0;
        bool isMultiplyByTwo = false;

        //Start the summing going right to left
        for (int index = digits.Length-1; index >= 0; --index) 
        {
            int digit = digits[index];

            //Every other digit should be multipled by two.
            if (isMultiplyByTwo) 
                digit *= 2;

            //When the digit becomes 2 digits (due to digit*2),
            //we add the two digits together.
            if (digit > 9) 
                digit = digit.ToString()
                  .Sum(character => (int)char.GetNumericValue(character));

            sum += digit;
            isMultiplyByTwo = !isMultiplyByTwo;
        }

        int remainder = sum % 10;

        //If theres no remainder, the checkDigit is 0.
        int checkDigit = 0; 

        //Otherwise, the checkDigit is the number that gets to the next 10
        if (remainder != 0)
            checkDigit = 10 - (sum % 10); 

        return checkDigit;
    }

An example of its use:

    public static bool IsValid(string userValue)
    {
        //Get the check digit from the end of the value
        int checkDigit = (int)char.GetNumericValue(userValue[userValue.Length - 1]);

        //Remove the checkDigit for the luhn calculation
        userValue = userValue.Substring(0, userValue.Length - 1); 
        int[] userValueDigits = userValue.Select(ch => (int)char.GetNumericValue(ch))
                                         .ToArray();

        int originalLuhnDigit = CalculateLuhnCheckDigit(userValueDigits);

        //If the user entered check digit matches the calcuated one,
        //the number is valid.
        return checkDigit == originalLuhnDigit;
    }

Porcupine

Answer 7

The parity check must start from the right.

Try this:

<?php

  function Luhn($digits) {

    $sum = 0;
    foreach (str_split(strrev($digits)) as $i => $digit) {
      $sum += ($i % 2 == 0) ? array_sum(str_split($digit * 2)) : $digit;
    }

    return $digits . (10 - ($sum % 10)) % 10;
  }

Add Luhn checksum to $input

  $digits = Luhn($input);
  

Verify a number with Luhn checksum in it:

  if ($digits == Luhn(substr($digits, 0, -1))) {
    // ... 
  }

Get the checksum number:

  $luhn_digit = substr(Luhn($digits), -1);

Ralaigh

Answer 8

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main()
{
    int *LONT, n, TARF;
    int SEGVT = 0;
    int SEGVT2 = 0;
    string TARJETA;
    double VA;

    cout << "cuantos digitos tiene la tarjeta: " << endl;
    cin >> n;

    LONT = new int[n];

    do {
        cout << "ingrese el # de la tarjeta: " << endl;
        cin >> TARJETA;
        VA = stod(TARJETA);
    } while (VA < 0);
    for (int POS = 0; POS < TARJETA.size(); POS++) {
        LONT[POS] = TARJETA[POS] - '0';
    }

    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            LONT[i] = TARJETA[i] - '0';
            LONT[i] = LONT[i] * 2;
            if (LONT[i] >= 10) {
                LONT[i] = LONT[i] - 9;
            }
            SEGVT2 = SEGVT2 + LONT[i];
        }
        else
        {
            LONT[i] = TARJETA[i] - '0';
            SEGVT = SEGVT + LONT[i];
        }
    }

    TARF = SEGVT + SEGVT2;
    if (TARF % 10 == 0) {
        cout << SEGVT2 << SEGVT;
        cout << "El numero de tarjeta " << TARJETA << "; Es de una tarjeta valida (YA QUE SU MOD10 ES " << TARF << endl;
    }
    else
    {
        cout << SEGVT2 << SEGVT;
        cout << "El numero de tarjeta" << TARJETA << "; No es de una tarjeta valida  (YA QUE SU MOD10 ES " << TARF << endl;
    }
    delete[] LONT;

}

Reservoir

Answer 9

My answer is for PHP Language

function isValdLuhn($str) {
    $sum = 0;
    $isSecond = false;
    for ($i = strlen($str); $i >= 1; $i--) {
        $num = $i - 1;
        if($isSecond) {
            $a = $str[$num] * 2;
            $sum += intdiv($a, 10) + $a%10;
        } else {
            $sum += $str[$num];
        }
        $isSecond = !$isSecond;
    }
    return $sum % 10 === 0 ? 'VALID' : 'INVALID';
}
isValdLuhn('8174060176912597');

Tarboosh