The Luhn Algorithm Explained

The Luhn algorithm, also known as the "modulus 10" or "mod 10" algorithm, is a simple checksum formula used to validate a variety of identification numbers, including South African ID numbers, credit card numbers, and IMEI numbers.

What is the Luhn Algorithm?

Invented by IBM scientist Hans Peter Luhn in 1954, the algorithm was designed to protect against accidental errors, such as mistyped digits. It's not meant to be a cryptographically secure hash—it won't protect against intentional fraud—but it catches most common transcription errors.

How It Works: Step by Step

Let's walk through validating a South African ID number: 8501015009087

Step 1: Write Out the Digits

Step 2: Double Every Second Digit (from the right)

Starting from the second-to-last digit and moving left, double every other digit:

Step 3: Subtract 9 from Results Over 9

If any doubled digit is greater than 9, subtract 9 from it (this is equivalent to adding the individual digits):

• 10 → 10 - 9 = 1
• 18 → 18 - 9 = 9
• 16 → 16 - 9 = 7

Step 4: Sum All Digits

Add all the resulting digits together:

Step 5: Check if Divisible by 10

If the sum is divisible by 10 (i.e., ends in 0), the number is valid:

JavaScript Implementation

Here's how to implement the Luhn algorithm in JavaScript:

function validateLuhn(idNumber) {
  // Remove any spaces or dashes
  const digits = idNumber.replace(/\D/g, '');

  let sum = 0;
  let isSecond = false;

  // Process from right to left
  for (let i = digits.length - 1; i >= 0; i--) {
    let digit = parseInt(digits[i], 10);

    if (isSecond) {
      digit *= 2;
      if (digit > 9) {
        digit -= 9;
      }
    }

    sum += digit;
    isSecond = !isSecond;
  }

  return sum % 10 === 0;
}

// Example usage
console.log(validateLuhn('8501015009087')); // true
console.log(validateLuhn('8501015009088')); // false

Common Uses of the Luhn Algorithm

• South African ID numbers - The 13th digit is the check digit
• Credit card numbers - Visa, Mastercard, Amex all use Luhn
• IMEI numbers - Mobile device identifiers
• National Provider Identifier - US healthcare
• Canadian Social Insurance Numbers

Limitations

While the Luhn algorithm is useful for catching typos, it has limitations:

• It cannot detect if two digits are swapped if they differ by 5 (e.g., 09 ↔ 90)
• It is not a security measure—anyone can generate a valid check digit
• It doesn't verify that an ID number actually exists or belongs to someone