Luhn algorithm
The Luhn algorithm, also known as the modulus 10 or mod 10 algorithm, is a simple checksum formula designed to validate multi-digit identification numbers by detecting common errors such as single-digit transcription mistakes or adjacent digit transpositions.[1] It achieves this by processing the digits of a number to produce a sum that must be divisible by 10 for the number to be valid.[2] Developed by IBM researcher Hans Peter Luhn, the algorithm was first described in U.S. Patent 2,950,048, filed on January 6, 1954, and issued on August 23, 1960.[3]
The core mechanism of the Luhn algorithm involves starting from the rightmost digit of the number (treating the check digit, if present, as the rightmost) and doubling every second digit moving leftward.[2] For each doubled value, if the result is 10 or greater, the tens digit is added to the units digit (or equivalently, subtract 9 from the value) to obtain a single digit; these adjusted values are then summed along with the undoubled digits.[2] The total sum is computed, and the number is valid if this sum modulo 10 equals 0.[4] To generate a check digit for a base number, the process is applied in reverse: the sum of the processed digits is calculated, and the check digit is the value (from 0 to 9) that makes the total sum divisible by 10.[3]
Widely adopted since its invention, the Luhn algorithm serves as a foundational error-detection tool in financial and identification systems, including the validation of credit and debit card numbers issued by major networks like Visa and Mastercard.[5] It is also employed for verifying other identifiers, such as International Mobile Equipment Identity (IMEI) numbers for mobile devices and National Provider Identifiers (NPIs) in U.S. healthcare.[1][4] While effective against all single-digit errors and nearly all transpositions of adjacent digits (which together account for about 90% of common transcription errors), it does not provide cryptographic security and is vulnerable to deliberate fraud if the check digit is guessed or bypassed.[2]
Overview
Definition and Purpose
The Luhn algorithm is a simple checksum formula used to validate identification numbers by generating or verifying a check digit appended to the sequence.[5][3] It was developed by Hans Peter Luhn, an IBM researcher, and patented in 1960.[6][3]
The primary purpose of the algorithm is to detect accidental errors during data entry or transmission, such as single-digit substitutions or transpositions of adjacent digits, while offering no protection against deliberate tampering.[5][2] It processes decimal digits from right to left, with the check digit serving as the rightmost element to ensure the overall sum meets a validation criterion.[3]
Historical Context
The Luhn algorithm was invented by Hans Peter Luhn, a researcher and engineer at IBM, who filed a U.S. patent application for a mechanical device to compute and verify check digits on January 6, 1954.[3] The patent, titled "Computer for Verifying Numbers," was granted on August 23, 1960, as U.S. Patent No. 2,950,048.[3] Luhn's work addressed the growing need for reliable error detection in early data processing environments, where manual entry and mechanical handling of numerical data were prone to mistakes such as digit transpositions or omissions.[7]
This development occurred amid IBM's dominance in punched-card systems for accounting and information management during the 1950s, when such technologies were essential for business operations like inventory tracking, billing, and order fulfillment.[8] Luhn's algorithm provided a simple, non-cryptographic method to append a check digit to multi-digit numbers, enabling quick validation without complex computations, which was particularly valuable for the era's electromechanical accounting machines.[9]
As credit card systems emerged in the late 1950s and expanded through the 1960s, the Luhn algorithm was integrated into early numbering schemes to ensure data integrity during manual and machine-based transactions. Its public domain status facilitated broad, royalty-free use across industries. Later, it was formalized in international standards, notably incorporated into ISO/IEC 7812-1:2017 as the prescribed method for computing check digits on identification cards, including those for financial applications.[10]
Algorithm Description
Step-by-Step Process
The Luhn algorithm operates on a sequence of decimal digits, where the rightmost digit serves as the check digit, and the doubling process begins on the second position from the right, ensuring consistent application regardless of the number's length. This positioning rule allows the algorithm to function uniformly for identification numbers of varying lengths, from short codes to longer account numbers, by always anchoring the check digit at the end.[2]
To validate a complete number using the Luhn algorithm, the process begins by identifying the check digit as the rightmost position and excluding it from initial processing. Starting from the right and moving leftward, every second digit (positions 2, 4, 6, etc., counting from the right) is doubled. For each doubled value, if the result exceeds 9, it is adjusted by subtracting 9 (equivalently, summing its individual digits to handle the carry). The unmodified digits in the odd positions (1, 3, 5, etc., from the right, excluding the check digit) remain as is. All processed doubled values and unmodified digits are then summed, and the check digit is added to this total. If the final sum is divisible by 10 (i.e., sum modulo 10 equals 0), the number is valid.[11]
For computing the check digit to append to a base number, the same preparatory steps are followed: exclude any existing check position, double every second digit from the right (starting at position 2), adjust doubled values greater than 9 by subtracting 9, and sum all processed and unmodified digits. The check digit is then calculated as (10 minus the sum modulo 10), taken modulo 10 to ensure it is a single digit from 0 to 9. This appends a value that makes the complete number's sum divisible by 10 when validated.[2]
The Luhn algorithm is defined for a sequence of digits d_n d_{n-1} \cdots d_1 d_0, where d_0 is the check digit and the indices correspond to positions from left to right, with position numbering starting from the rightmost digit as position 1 (d_0).
Positions are counted from the right, with odd-numbered positions (1, 3, 5, ...) using the digit as is and even-numbered positions (2, 4, 6, ...) applying a doubling transformation.[11]
The doubling function is formally f(x) = x if x \leq 9, and f(x) = x - 9 if $10 \leq x \leq 18 (since x = 2d for digit d \in \{0, \dots, 9\}).
The validation sum is then
S = \sum_{\substack{k=1 \\ k \ odd}}^{n+1} d_{k-1} + \sum_{\substack{k=2 \\ k \ even}}^{n+1} f(2 d_{k-1}),
where the number is valid if S \equiv 0 \pmod{10}.[11]
To derive the check digit d_0, compute the partial sum S' over d_n \cdots d_1 (with positions shifted rightward, so the new rightmost d_1 is now in odd position 1), then set d_0 = (10 - (S' \mod 10)) \mod 10.[2]
This modulo-10 property ensures the total sum S is a multiple of 10 for valid numbers, providing a simple congruence check for integrity.[3]
A proof sketch for its transposition detection capability considers swapping adjacent digits a (in an odd position, weight 1) and b (in an even position, weight effectively 2 via f): the change in sum is (b - a) + f(2a) - f(2b), which simplifies to (a - b) + 9(\delta_b - \delta_a) where \delta_d = 1 if d \geq 5 else 0; this difference is nonzero modulo 10 for all distinct digit pairs except specific cases like 0 and 9, where the sum remains unchanged.[2]
Examples
Computing the Check Digit
To compute the check digit, process the base number from right to left, doubling every second digit starting with the rightmost digit of the base (which will become the second position from the right in the full number), and apply the digit sum rule (sum digits or subtract 9) to any doubled value of 10 or greater. Calculate the sum of all processed digits; the check digit is the smallest non-negative integer (0-9) that makes the total sum divisible by 10.[3]
Consider the base number 7992739871 as an example. The positions to double are the 1st, 3rd, 5th, 7th, and 9th from the right: digits 1, 8, 3, 2, 9. The doubled values are: 1×2=2, 8×2=16 (1+6=7), 3×2=6, 2×2=4, 9×2=18 (1+8=9). The non-doubled digits sum to 7+7+9+7+9=39? Wait, digits: from left 7,9,9,2,7,3,9,8,7,1; non-doubled pos2=7, pos4=9, pos6=7, pos8=9, pos10=7 sum 7+9+7+9+7=39. Processed doubled: 2+7+6+4+9=28. Total sum=39+28=67. The check digit is 10 − (67 mod 10) = 10 − 7 = 3, resulting in the full number 79927398713.
The following table illustrates the process for the base number, with positions numbered from the right (pos1 rightmost, doubled), running sum accumulated from right to left:
| Position from right | Digit | Doubled? | Processed Value | Running Sum |
|---|
| 1 | 1 | Yes | 2 | 2 |
| 2 | 7 | No | 7 | 9 |
| 3 | 8 | Yes | 7 | 16 |
| 4 | 9 | No | 9 | 25 |
| 5 | 3 | Yes | 6 | 31 |
| 6 | 7 | No | 7 | 38 |
| 7 | 2 | Yes | 4 | 42 |
| 8 | 9 | No | 9 | 51 |
| 9 | 9 | Yes | 9 | 60 |
| 10 | 7 | No | 7 | 67 |
Validating an Identification Number
To validate an identification number using the Luhn algorithm, process the entire number from right to left, doubling every second digit starting from the second position from the right (results over 9 reduced by summing digits or subtracting 9), sum all processed values; the number is valid if the total modulo 10 equals 0.[3] This confirms the check digit balances the preceding digits.
Consider the complete number 79927398713. The processed values sum to 70, and 70 mod 10 = 0, so valid.[12]
The following table illustrates the step-by-step processing for 79927398713, positions from the right (position 1 rightmost, not doubled):
| Position (from right) | Digit | Double? | Processed Value |
|---|
| 1 | 3 | No | 3 |
| 2 | 1 | Yes | 2 (1×2) |
| 3 | 7 | No | 7 |
| 4 | 8 | Yes | 7 (8×2=16, 1+6) |
| 5 | 9 | No | 9 |
| 6 | 3 | Yes | 6 (3×2) |
| 7 | 7 | No | 7 |
| 8 | 2 | Yes | 4 (2×2) |
| 9 | 9 | No | 9 |
| 10 | 9 | Yes | 9 (9×2=18, 1+8) |
| 11 | 7 | No | 7 |
Implementation
The Luhn algorithm can be expressed in pseudocode to illustrate its core logic for both validating a complete number (including its check digit) and computing a check digit for a partial number. These representations assume the input is a string of digits, preserving leading zeros if present, and process the digits from right to left for consistency with common implementations. The validation function computes a weighted sum where every second digit (starting from the rightmost, which is position 1 and remains undoubled) is doubled and adjusted if necessary, then checks if the total sum is divisible by 10.[3]
For edge cases, an empty string or single-digit input should return false for validation (as they lack sufficient digits for meaningful checking) or indicate invalid input for check digit computation. The following pseudocode outlines these operations in a language-agnostic manner.
Validation Pseudocode
function isValid(number: [string](/page/String)): [boolean](/page/Boolean)
if length(number) < 2 then
return false // Edge case: too few digits
end if
sum = 0
isEvenPosition = false // Starting from right: position 1 (rightmost) is odd, no double
for i = length(number) - 1 downto 0 do // Process from right to left
digit = integer(number[i])
if isEvenPosition then
doubled = 2 * digit
sum += if doubled > 9 then doubled - 9 else doubled
else
sum += digit
end if
isEvenPosition = not isEvenPosition
end for
return sum % 10 == 0
end [function](/page/Function)
function isValid(number: [string](/page/String)): [boolean](/page/Boolean)
if length(number) < 2 then
return false // Edge case: too few digits
end if
sum = 0
isEvenPosition = false // Starting from right: position 1 (rightmost) is odd, no double
for i = length(number) - 1 downto 0 do // Process from right to left
digit = integer(number[i])
if isEvenPosition then
doubled = 2 * digit
sum += if doubled > 9 then doubled - 9 else doubled
else
sum += digit
end if
isEvenPosition = not isEvenPosition
end for
return sum % 10 == 0
end [function](/page/Function)
This pseudocode reverses the processing direction implicitly by iterating from the end, ensuring the rightmost digit is not doubled, as described in the original method for error detection.[3]
Check Digit Computation Pseudocode
function computeCheckDigit(number: string): [integer](/page/Integer)
if [length](/page/Length)(number) == 0 then
return -1 // [Edge case](/page/Edge_case): invalid input
end if
sum = 0
isEvenPosition = true // Starting from right of base: rightmost base [digit](/page/Digit) is position 2 in full number (even, double)
for i = [length](/page/Length)(number) - 1 downto 0 do
[digit](/page/Digit) = [integer](/page/Integer)(number[i])
if isEvenPosition then
doubled = 2 * [digit](/page/Digit)
sum += if doubled > 9 then doubled - 9 else doubled
else
sum += [digit](/page/Digit)
end if
isEvenPosition = not isEvenPosition
end for
checkDigit = (10 - (sum % 10)) % 10
return checkDigit
end function
function computeCheckDigit(number: string): [integer](/page/Integer)
if [length](/page/Length)(number) == 0 then
return -1 // [Edge case](/page/Edge_case): invalid input
end if
sum = 0
isEvenPosition = true // Starting from right of base: rightmost base [digit](/page/Digit) is position 2 in full number (even, double)
for i = [length](/page/Length)(number) - 1 downto 0 do
[digit](/page/Digit) = [integer](/page/Integer)(number[i])
if isEvenPosition then
doubled = 2 * [digit](/page/Digit)
sum += if doubled > 9 then doubled - 9 else doubled
else
sum += [digit](/page/Digit)
end if
isEvenPosition = not isEvenPosition
end for
checkDigit = (10 - (sum % 10)) % 10
return checkDigit
end function
The computation excludes the check digit position, treating the input as the base number, and derives the digit that would make the full sum divisible by 10 when appended. This mirrors the validation logic but solves for the final digit.[3]
Practical Considerations
The Luhn algorithm operates with O(n time complexity, where n represents the number of digits in the input, as it requires a single pass through the sequence to compute the checksum.[12] This efficiency ensures minimal computational overhead, making it ideal for real-time validation in payment processing systems, where it enables instant error detection without significant delays.[5][1]
Implementations in various programming languages leverage built-in functions for concise execution. In Python, a typical validation function processes the digits in reverse and applies the doubling rule selectively:
python
def is_luhn_valid(number):
digits = [int(d) for d in str(number)][::-1]
total = 0
for i, d in enumerate(digits):
if i % 2 == 1:
d *= 2
if d > 9:
d -= 9
total += d
return total % 10 == 0
def is_luhn_valid(number):
digits = [int(d) for d in str(number)][::-1]
total = 0
for i, d in enumerate(digits):
if i % 2 == 1:
d *= 2
if d > 9:
d -= 9
total += d
return total % 10 == 0
[12]
In JavaScript, the reduce method facilitates a functional approach:
javascript
function isLuhnValid(number) {
const digits = number.toString().split('').reverse().map(Number);
const sum = digits.reduce((acc, digit, i) => {
let val = digit;
if (i % 2 === 1) {
val *= 2;
if (val > 9) val -= 9;
}
return acc + val;
}, 0);
return sum % 10 === 0;
}
function isLuhnValid(number) {
const digits = number.toString().split('').reverse().map(Number);
const sum = digits.reduce((acc, digit, i) => {
let val = digit;
if (i % 2 === 1) {
val *= 2;
if (val > 9) val -= 9;
}
return acc + val;
}, 0);
return sum % 10 === 0;
}
[12]
Error handling is crucial in practical deployments; functions must reject non-numeric inputs by validating that the provided string consists solely of digits, preventing invalid computations.[5] The algorithm inherently supports variable-length inputs without requiring a fixed modulo beyond base 10, accommodating identifiers from 10 to 19 digits or more.[12]
For enhanced performance in scenarios like user input streams, optimizations avoid full string reversal by iterating from the right and maintaining a running total, allowing incremental processing as digits arrive.[2] This approach aligns with the core pseudocode logic while reducing memory operations for large or dynamic inputs.
Testing implementations should include unit tests for valid numbers, single-digit errors, and adjacent transpositions, as the algorithm detects nearly all such common input mistakes to ensure reliability in production environments.[2]
Applications
Common Uses in Identification Systems
The Luhn algorithm is prominently employed in credit and debit card systems to validate Primary Account Numbers (PANs), as specified in the ISO/IEC 7812-1 standard, which mandates its use for error detection during data entry.[13] This application helps identify common transcription errors, such as single-digit mistakes or transpositions, in the 16-digit card numbers issued by networks like Visa and Mastercard.[5] Given the scale of global payment processing, the algorithm performs billions of validations daily across these networks, safeguarding transactions worth trillions of dollars annually.[14]
In government-issued identification systems, the Luhn algorithm generates the check digit for International Mobile Equipment Identity (IMEI) numbers, a 15-digit code unique to mobile devices that facilitates tracking and authentication by telecom authorities.[15] This ensures the integrity of IMEI entries in databases used for device registration and anti-theft measures worldwide.[16] It is also used for the National Provider Identifier (NPI) in U.S. healthcare, a 10-digit number for providers where the final digit is the Luhn check digit.[4] While not universally applied to all national IDs, it appears in select systems for partial validation of numeric identifiers, such as the Canadian Social Insurance Number, which applies standard Luhn validation to its nine digits.[17]
Beyond financial and telecom sectors, the Luhn algorithm supports validation in loyalty programs, where it computes check digits for member account numbers to prevent input errors during point accrual and redemption.[18] For instance, certain retail and hospitality schemes embed it in 16-digit loyalty cards to maintain data accuracy in customer databases.
As of 2025, the algorithm remains integral to modern digital ecosystems, embedded in mobile wallet applications like Apple Pay and Google Pay for real-time card number verification during tokenization, as well as in e-commerce APIs from providers such as Stripe to flag invalid entries before processing.[5] This integration enhances user experience by reducing failed transactions in high-volume online environments.[19]
Variants and Extensions
The Luhn algorithm serves as a foundation for several generalizations and modifications aimed at improving error detection rates or accommodating non-decimal data.
A notable generalization is the Luhn mod N algorithm, which extends the original method to work with sequences in any even-numbered base N, enabling validation of alphanumeric or symbolic strings by mapping characters to values from 0 to N-1 and applying the doubling and summing process modulo N. This variant is particularly useful for identification systems involving non-numeric characters, such as certain product codes or addresses.[20]
The Verhoeff algorithm represents a more advanced extension for decimal systems, developed in 1969 using the dihedral group D_5 to generate permutation tables for weighted multiplication and addition, achieving detection of all single-digit errors, all adjacent transpositions, and most other common transcription errors—capabilities beyond the standard Luhn method.[21][22]
Another significant variant is the Damm algorithm, introduced by H. Michael Damm in 2007, which employs a totally anti-symmetric quasigroup of order 10 defined by a specific multiplication table to compute the check digit, ensuring detection of all single-digit errors and all adjacent transpositions without the need for doubling or complex weights.[23] This approach offers error detection performance comparable to Verhoeff but with simpler implementation for decimal codes.
Weighted variants modify the core Luhn weighting scheme (alternating 1 and 2) by applying custom sequences, such as 1,3,1,3,... or increasing weights like 2,3,4,...,9,1 for modulo 10 or 11 arithmetic, to enhance detection of specific error patterns in identification numbers like ISBNs or national IDs.[21] For instance, ISBN-13 uses a Luhn variant with alternating weights of 1 and 3 modulo 10, while the modulus 11 weighted scheme with weights 2 through 10 detects nearly all single errors and transpositions when used with a check digit from 0-9 or X for 10.
Some identification systems apply variants of the Luhn algorithm, such as computing check digits for portions of longer numbers, to enhance error detection in national ID formats.[21]
Strengths and Limitations
Detection Strengths
The Luhn algorithm excels at detecting accidental errors in identification numbers, particularly those arising from human input mistakes, due to its design leveraging modulo 10 arithmetic to validate the overall checksum. It reliably identifies all single-digit substitution errors, where one digit is incorrectly entered as another value, because each digit's contribution to the weighted sum is unique modulo 10, ensuring that any change results in a non-zero difference modulo 10. The only exception is a trivial error of zero change (replacing a digit with itself), which is not an actual error and thus rare in practice.[21]
For adjacent digit transpositions—a common typing error where two neighboring digits are swapped—the algorithm detects nearly all cases, failing only on specific pairs where the digits differ by 9, such as 09 ↔ 90. In this example, assuming the left digit (0) is doubled to 0 and the right (9) remains 9, the sum is 9; after swapping to 90, the doubled 9 becomes 18 (reduced to 9) and the 0 remains 0, yielding the same sum of 9 modulo 10. This non-detection occurs because the doubling and reduction step (subtracting 9 for values ≥10) preserves the checksum for such pairs regardless of position weights. In random data, the algorithm catches approximately 98% of these transposition errors, as only about 2% of possible adjacent pairs (09 and 90) evade detection out of 90 potential error transpositions.[21][24]
While effective against single and most transposition errors, the Luhn algorithm does not detect all multiple-digit errors, such as certain twin errors where two non-adjacent digits are altered in a way that the net change to the sum is a multiple of 10. These limitations arise from the modulo 10 properties, where compensating errors can align to preserve the checksum, though the algorithm still catches the vast majority (around 90%) of common random errors overall.[21][25]
Security Weaknesses
The Luhn algorithm exhibits significant vulnerabilities to intentional fraud, primarily because it allows attackers to easily generate valid-appearing identification numbers by computing the check digit for any arbitrary sequence of digits. This process requires no encryption or data obscuration, enabling fraudsters to produce batches of plausible fakes using simple software tools that exploit the deterministic nature of the checksum calculation. For example, partial knowledge of a credit card number—such as the bank identification number and account details—can be leveraged to create numerous valid combinations, facilitating unauthorized transactions at point-of-sale terminals or online.[26][2]
The algorithm also fails to detect specific types of deliberate modifications designed to preserve the checksum, such as non-adjacent transpositions (jump transpositions) or multi-digit substitutions where the net change in the weighted sum is a multiple of 10. These "jumps" or balanced alterations allow fraudsters to tweak numbers without triggering validation failure, contrasting with its higher efficacy against accidental errors. Although the Luhn method identifies approximately 90% of random input errors, this detection rate underscores its limitations when facing crafted attacks.[27][28]
In 2025, the Luhn algorithm alone is inadequate for cybersecurity in payment systems, where it serves merely as a basic format check and must be paired with stronger measures like Card Verification Values (CVV), EMV chip authentication, and tokenization to counter fraud effectively. Under EMV standards, tokens mimic primary account numbers by incorporating a Luhn-compliant check digit but restrict data exposure through domain controls and cryptographic binding, addressing the algorithm's inability to authenticate or secure the underlying information. Early credit card fraud in the 1970s frequently bypassed such validations by recalculating check digits for counterfeit cards, a tactic that remains viable without layered defenses.[29][2]
Due to these weaknesses, the Luhn algorithm should be employed solely as a preliminary filter for error-prone inputs, never as the primary security mechanism, with comprehensive systems incorporating multi-factor authentication and real-time fraud monitoring to mitigate risks.[5][2]