The Quick and Dirty Genius of Luhn Algorithm

After working in financial industry for a while you kind of become desensitised to lots of financial concepts or terminology. I realized it when I learned about a Luhn Algorithm or Luhn Check. This algorithm is a very basic checksum algorithm that works every time we input our credit or debit card numbers. In addition to that, it turns out that a wide variety of other businesses and industries utilize this simple check.

What is Luhn Algorithm?

What Luhn Check does is it verifies that a number that is longer than two digits is entered correctly. It accomplishes it through a series of simple calculations which create a check digit. Usually this check digit gets attached to the number at the end, and is then used for verification purpose. The same calculation happens to verify the number sequence. And if the number is correct, then the calculated check digit will match the last digit of the number. This approach allows the numbers to have their checksum appended at the end, and results in this built-in mechanism to check for the validity of the entered number.

Here is an example from Wikipedia that breaks down the calculation on a number:

Assume an example of an account number 1789372997 (just the “payload”, check digit not yet included):

Use Cases

Fun fact: according to the aforementioned source, the Luhn algorithm is used in a variety of systems, including:

• Credit card numbers
• IMEI numbers
• CUSIP numbers for North American financial instruments
• National Provider Identifier numbers in the United States
• Canadian social insurance numbers
• Israeli ID numbers
• South African ID numbers
• South African Tax reference numbers
• Swedish Personal identity numbers
• Swedish Corporate Identity Numbers (OrgNr)
• Greek Social Security Numbers (ΑΜΚΑ)
• ICCID of SIM cards
• European patent application numbers
• Survey codes appearing on McDonald’s, Taco Bell, and Tractor Supply Co. receipts
• United States Postal Service package tracking numbers use a modified Luhn algorithm
• Italian VAT numbers (Partita Iva)

Sample Implementation of Luhn Algorithm in Go

I decided to implement this algorithm using Go. I created a package that could be imported in any project to use that function instantly. Here is what the core logic code looks like:

package main

import (
	"strconv"
)

// Pseudocode for Luhn Algorithm
// Source: https://en.wikipedia.org/wiki/Luhn_algorithm
//
// function isValid(cardNumber[1..length])
//     sum := 0
//     parity := length mod 2
//     for i from 1 to (length - 1) do
//         if i mod 2 == parity then
//             sum := sum + cardNumber[i]
//         elseif cardNumber[i] > 4 then
//             sum := sum + 2 * cardNumber[i] - 9
//         else
//             sum := sum + 2 * cardNumber[i]
//         end if
//     end for
//     return cardNumber[length] == ((10 - (sum mod 10)) mod 10)
// end function

func isValid(num string) (bool, error) {
	if len(num) < 1 {
		return false, nil
	}
	checkDigit, err := getCheckDigit(num[0 : len(num)-1])
	if err != nil {
		return false, err
	}
	return string(num[len(num)-1]) == checkDigit, nil
}

func getCheckDigit(num string) (string, error) {
	if len(num) < 1 {
		return "", nil
	}
	sum := 0
	parity := len(num) % 2
	for i := range len(num) {
		digit, err := strconv.Atoi(string(num[i]))
		if err != nil {
			return "", err
		}
		if i%2 == parity {
			sum += digit
		} else if digit > 4 {
			sum += 2*digit - 9
		} else {
			sum += 2 * digit
		}
	}
	return strconv.Itoa((10 - (sum % 10)) % 10), nil
}

The validation code does the following:

1. Checks that the number is present
2. Calculates the checksum digit using the algorithm
3. Compares the result with the last digit of the number

Usage

To use this package you will need to have Go 1.24.2 or later. There are several ways to get started with this package: interactive, batch, library. To start using this package you will need to install it from source or use with go install.

Install from source

git clone https://github.com/EvgeniiKlepilin/luhn-go.git
cd luhn-go
go build -o luhn

Install directly with go install

go install github.com/EvgeniiKlepilin/luhn-go@latest

Command Line Interface

Interactive Mode

Run the program without arguments to enter interactive mode:

You’ll be prompted to enter a number:

Please enter a number to validate:
4826493525582251
Validating 4826493525582251
Number 4826493525582251 is valid.

Batch Mode

Validate multiple numbers by passing them as command-line arguments:

./luhn 4826493525582251 373068810980009 5412769127028265

Output:

Validating the following numbers: [4826493525582251 373068810980009 5412769127028265]
Number 4826493525582251 is valid.
Number 373068810980009 is valid.
Number 5412769127028265 is valid.

Single Number Validation

As a Go Library

You can also use this package as a library in your Go applications:

package main

import (
    "fmt"
    "github.com/EvgeniiKlepilin/luhn-go"
)

func main() {
    // Validate a credit card number
    valid, err := isValid("4826493525582251")
    if err != nil {
        fmt.Printf("Error: %v\n", err)
        return
    }
    
    if valid {
        fmt.Println("Card number is valid!")
    } else {
        fmt.Println("Card number is invalid.")
    }
    
    // Generate a check digit
    checkDigit, err := getCheckDigit("482649352558225")
    if err != nil {
        fmt.Printf("Error: %v\n", err)
        return
    }
    
    fmt.Printf("Check digit: %s\n", checkDigit) // Output: Check digit: 1
}

For more information about the package, please go to https://github.com/EvgeniiKlepilin/luhn-go.

Why this simple algorithm is awesome

This algorithm is not a complex hash function that could be relied on for data integrity. Not by a long shot. The beauty of this simple algorithm lies in its simplicity to provide quick and dirty integrity check with the smallest need for calculation, especially when compared to the cryptographically secure checksums and hash functions. This check can happen as soon as the user enters that number in the input field, and the inline error would appear to prompt the user to double check their entry. No need for server requests or for more complex client-side calculations. I just think that this is a very clever and simple trick to quickly verify a long number sequence. If the user were to misplace any digits or swap some of them, the check digit would be different and the feedback would be instant.

Checksum Collisions

To be fair, a checksum collision can occur here. A checksum collision or a hash collision refers to an event when two different sets of data result in the same hash or checksum. Generally, the simpler the algorithm, the more hash collisions can occur. So this has to be kept in mind when talking about a hashing algorithm.

If we were to use Luhn Check on the numbers 0123456789 and 9123456780, both would result in a checksum of value 7. Another weakness that it has is the failure to detect a double digit error in conjunction with specific pairs: 22 <-> 55, 33 <-> 66, 44 <-> 77. For instance, numbers 001144 and 001177 will have the same checksum.

Going on a tangent

I think that in the modern age of AI and incredible computing powers that are wielded by pretty much anyone who has a smartphone, we no longer search for smart and optimal solutions that creatively address niche needs under constraints. Most of the time this algorithm would not even be considered because we can simply send a server request to double check the existing number for us, and it would take marginally longer than when done locally. It is even witnessed in the way the end consumers operate technology - we no longer look for an article that answers our question and was written long time ago - we go straight to ChatGPT and ask it to search the web or generate the answer on-the-fly for a trivial question that has been answered 10 years ago. That is so much more computationally intensive than requesting a web page of an article from a trusted author. I am often guilty of this myself.

I love finding simple and clever solutions and algorithms like Luhn Check that display ingenuity and creativity of accomplishing a task under heavy constraints. I am not someone who has come up with many simple and smart solutions myself, but I very much admire and look up to them. This example serves as an encouragement to me to look for ways to get a task done that doesn’t require many resources, but instead can be done simply and effectively. I hope it encourages you too.