Luhn's Algorithm

Luhn's algorithm, also known as "modulus 10", is a checksum formula that is widely used across different industries, such as financial firm and governments.

# How it works

Luhn's algorithm can be broken down into a few simple steps. Let's say we have a credit card number "374245455400126".

1. Separate the payload and the check digit. The check digit is the last digit. This yields "37424545540012" and "6".
2. Starting from the last digit "2", moving from right to left, for every second digit, multiply it by two. If the result of the multiplication exceeded 9, deduct 9 from it to make it within 10.
3. Add the resultant numbers to the total sum.

4. Calculate the check digit by the following formula

As you can see, the check digit is equivalent to the value extracted from the original card number, which is 6. This shows that the card number is valid.

# Implementation

This is the implementation of the algorithm in C#. The parity is used to determine whether to double the digit or not.

public static bool ValidateLuhn(string cardNumber)
{
    int sum = 0;
    int parity = (cardNumber.Length - 1) % 2;

    // The `- '0'` converts char digit to int digit
    int checkDigit = cardNumber[^1] - '0';

    for (int i = cardNumber.Length - 2; i >= 0; i--)
    {
        int digit = cardNumber[i] - '0';

        if (i % 2 == parity)
        {
            sum += digit;
        }
        else if (digit > 4)
        {
            sum += (2 * digit) - 9;
        }
        else
        {
            sum += 2 * digit;
        }
    }

    return checkDigit == 10 - (sum % 10);
}

The implementation above can be further simplified by summing all the digits (still respecting the rule for doubling) of the string and checks whether the resulting sum has no remainder when divided by 10. If there is no remainder, means the number is valid.

public static bool ValidateLuhn(string cardNumber)
{
    int sum = 0;
    int parity = cardNumber.Length % 2;

    for (int i = 0; i < cardNumber.Length; i++)
    {
        int digit = cardNumber[i] - '0';

        if (i % 2 != parity)
        {
            sum += digit;
        }
        else if (digit > 4)
        {
            sum += (2 * digit) - 9;
        }
        else
        {
            sum += 2 * digit;
        }
    }

    return sum % 10 == 0;
}

# Disadvantages

As Luhn Algorithm is used to distinguish the validity of a string of numbers from mistyping, it is not tamper-proof. Moreover, it is great at capturing single-digit error but is bad at capturing multi-digit errors.

# Tools

• https://paymentcardtools.com/luhn-algorithm
• https://developers.bluesnap.com/reference/test-credit-cards

# References