Wikipedia

Luhn algorithm: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Fix buggy C# implementation which was giving an incorrect answer for arrays of odd length. E.g. it was returning `false` for "49927398716"
No edit summary
 
(29 intermediate revisions by 26 users not shown)
Line 1:
{{Short description|Simple checksum formula}}
{{redirects|Luhn|people named Luhn|Luhn (surname)}}
The '''Luhn algorithm''' or '''Luhn formula''' (creator: [[IBM]] scientist [[Hans Peter Luhn]]), also known as the "[[modular arithmetic|modulus]] 10" or "mod 10" [[algorithm]], is a simple [[check digit]] formula used to validate a variety of identification numbers. {{efn|It is described in [[United States|US]] patent 2950048A, granted on {{date|1960-08-23|DMY}}.<ref name="US2950048A">{{cite patent|title=Computer for Verifying Numbers|country=US|number=2950048A|status=patent|pubdate={{date|1960-08-23|DMY}}|gdate={{date|1960-08-23|DMY}}|invent1=Luhn|inventor1-first=Hans Peter|fdate=1954-01-06|inventorlink=Hans Peter Luhn}}</ref>}}
 
The algorithm is in the [[public ___domain]] and is in wide use today. It is specified in [[ISO/IEC 7812-1]].<ref>{{cite tech report|title=Identification cards {{mdash}} Identification of issuers {{mdash}} Part 1: Numbering system|number=[[ISO/IEC 7812]]-1:{{date|2017|DMY}}|institution=[[International Organization for Standardization]] & [[International Electrotechnical Commission]]|date={{date|Jan 2017|DMY}}|type=standard|url=https://www.iso.org/standard/70484.html|chapter=Annex B: Luhn formula for computing modulus-10 “double-add-double” check digits}}</ref> It is not intended to be a [[cryptographic hash function|cryptographically secure hash function]]; it was designed to protect against accidental errors, not malicious attacks. Most [[credit card number]]s and many [[government identification numbers]] use the algorithm as a simple method of distinguishing valid numbers from mistyped or otherwise incorrect numbers.
The '''Luhn algorithm''' or '''Luhn formula''', also known as the "[[modular arithmetic|modulus]] 10" or "mod 10" [[algorithm]], named after its creator, [[IBM]] scientist [[Hans Peter Luhn]], is a simple [[check digit]] formula used to validate a variety of identification numbers. It is described in [[United States|US]] patent 2950048A, granted on {{date|1960-08-23|DMY}}.<ref name="US2950048A">{{cite patent|title=Computer for Verifying Numbers|country=US|number=2950048A|status=patent|pubdate={{date|1960-08-23|DMY}}|gdate={{date|1960-08-23|DMY}}|invent1=Luhn|inventor1-first=Hans Peter|fdate=1954-01-06|inventorlink=Hans Peter Luhn}}</ref>
 
The algorithm is in the [[public ___domain]] and is in wide use today. It is specified in [[ISO/IEC 7812-1]].<ref>{{cite tech report|title=Identification cards {{mdash}} Identification of issuers {{mdash}} Part 1: Numbering system|number=[[ISO/IEC 7812]]-1:{{date|2017|DMY}}|institution=[[International Organization for Standardization]] & [[International Electrotechnical Commission]]|date={{date|Jan 2017|DMY}}|type=standard|url=https://www.iso.org/standard/70484.html|chapter=Annex B: Luhn formula for computing modulus-10 “double-add-double” check digits}}</ref> It is not intended to be a [[cryptographic hash function|cryptographically secure hash function]]; it was designed to protect against accidental errors, not malicious attacks. Most credit cards and many government identification numbers use the algorithm as a simple method of distinguishing valid numbers from mistyped or otherwise incorrect numbers.
 
==Description==
The check digit is computed as follows:
# If the number already containsDrop the check digit, dropfrom thatthe digitnumber to(if formit's thealready "payload"present). TheThis check digit is most oftenleaves the last digitpayload.
# WithStart with the payload digits. Moving from right to left, startdouble every second digit, starting from the rightmostlast digit. MovingIf left,doubling doublea thedigit results in a value of> every9, secondsubtract digit9 from it (includingor thesum rightmostits digitdigits).
# Sum all the valuesresulting ofdigits (including the resultingones digitsthat were not doubled).
# The check digit is calculated by <math>(10 - (s \bmod 10)) \bmod 10</math>, where s is the sum from step 3. This is the smallest number (possibly zero) that must be added to <math>s</math> to make a multiple of 10. Other valid formulas giving the same value are <math>9 - ((s + 9)\bmod 10)</math>, <math>(10 - s)\bmod 10</math>, and <math>10\lceil s/10\rceil - s</math>. Note that the formula <math>(10 - s)\bmod 10</math> will not work in all environments due to differences in how negative numbers are handled by the [[modulo]] operation.
 
=== Example for computing check digit ===
Line 16:
Assume an example of an account number 1789372997 (just the "payload", check digit not yet included):
 
{| class="wikitable" style="text-align:center;border:none;background:transparent;"4353464434047422| style="width:1.5em" | 4283039836977353| style="width:1.5em" | 9
|! style="width:1.5em" | Digits reversed
| style="width:1.5em" | 7
| style="width:1.5em" | 9
Line 54:
|-
!
| style="background: #FFA; color: #000;" | '''14'''
| 9
| style="background: #FFA; color: #000;" | '''18'''
| 2
| style="background: #FFA; color: #000;" | '''14'''
| 3
| style="background: #FFA; color: #000;" | '''18'''
| 8
| style="background: #FFA; color: #000;" | '''14'''
| 1
|-
! Sum digits
|'''5''' <br> (1+4)
|9 <br> &nbsp;
|9
|'''9''' <br> (1+8)
|2 <br> &nbsp;
|2
|'''5''' <br> (1+4)
|3 <br> &nbsp;
|3
|'''9''' <br> (1+8)
|8 <br> &nbsp;
|8
|'''5''' <br> (1+4)
|1 <br> &nbsp;
|1
|}
 
The sum of the resulting digits is 56.
 
The check digit is equal to <math>(10 - (56 \operatorname{mod}bmod 10))\bmod 10 = 4</math>.
 
This makes the full account number read 17893729974.
Line 106:
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'''
Line 115:
'''end if'''
'''end for'''
'''return''' cardNumber[length] == ((10 - (sum mod 10)) mod 10)
'''end function'''
 
== Code implementation ==
 
=== [[C Sharp (programming language)|C#]] ===
<syntaxhighlight lang="c#" line="1">
bool IsValidLuhn(int[] digits)
{
int checkDigit = 0;
for (int i = digits.Length - 2; i >= 0; --i)
{
checkDigit +=
(i & 1) == (digits.Length & 1)
? digits[i] > 4 ? digits[i] * 2 - 9 : digits[i] * 2
: digits[i];
}
 
return (10 - checkDigit % 10) % 10 == digits[^1];
}
</syntaxhighlight>
 
=== [[Java (programming language)|Java]] ===
<syntaxhighlight lang="java" line="1">
public static boolean isValidLuhn(String number) {
int n = number.length();
int total = 0;
boolean even = true;
// iterate from right to left, double every 'even' value
for (int i = n - 2; i >= 0; i--) {
int digit = number.charAt(i) - '0';
if (digit < 0 || digit > 9) {
// value may only contain digits
return false;
}
if (even) {
digit <<= 1; // double value
}
even = !even;
total += digit > 9 ? digit - 9 : digit;
}
int checksum = number.charAt(n - 1) - '0';
return (total + checksum) % 10 == 0;
}
</syntaxhighlight>
 
=== [[TypeScript]] ===
<syntaxhighlight lang="typescript" line="1">
function luhnCheck(input: number): boolean {
const number = input.toString();
const digits = number.replace(/\D/g, '').split('').map(Number);
let sum = 0;
let isSecond = false;
for (let i = digits.length - 1; i >= 0; i--) {
let digit = digits[i];
if (isSecond) {
digit *= 2;
if (digit > 9) {
digit -= 9;
}
}
sum += digit;
isSecond = !isSecond;
}
return sum % 10 === 0;
}
</syntaxhighlight>
=== [[Python (programming language)|Python]] ===
{{unbulleted list|[[File:Apache Feather Logo.svg|12px|class=noviewer|link=|alt=Apache-2.0]] This section incorporates source code from [[Git]] repository {{URL|https://github.com/codeperfectplus/Sanatio.git}} on [[GitHub]], which is licensed under the [[Apache License]], Version 2.0, copyright © 2022{{ndash}}2024 codeperfectplus, 2024 troyfigiel.<ref>{{Cite web |last=Raj |first=Deepak |last2=Figiel |first2=Troy |date=14 November 2022 |title=Verhoeff's algorithm implementation for checksum digit calculation |url=https://github.com/codeperfectplus/Sanatio/blob/d5d4f22636cc68ba817eed28364d63eafc2d30ec/sanatio/utils/checksum.py |url-status=live |archive-url=https://web.archive.org/web/20240725101147/https://github.com/codeperfectplus/Sanatio/blob/d5d4f22636cc68ba817eed28364d63eafc2d30ec/sanatio/utils/checksum.py |archive-date=25 July 2024 |access-date=25 July 2024 |website=[[GitHub]]}}</ref>}}
 
<syntaxhighlight lang="python" line="1">
"""Verhoeff's algorithm implementation for checksum digit calculation"""
 
 
class LuhnAlgorithm(BaseChecksumAlgorithm):
"""
Class to validate a number using Luhn algorithm.
 
Arguments:
input_value (str): The input value to validate.
 
Returns:
bool: True if the number is valid, False otherwise.
"""
def __init__(self, input_value: str) -> None:
self.input_value = input_value.replace(' ', '')
 
def last_digit_and_remaining_numbers(self) -> tuple:
"""Returns the last digit and the remaining numbers"""
return int(self.input_value[-1]), self.input_value[:-1]
 
def __checksum(self) -> int:
last_digit, remaining_numbers = self.last_digit_and_remaining_numbers()
nums = [int(num) if idx % 2 != 0 else int(num) * 2 if int(num) * 2 <= 9
else int(num) * 2 % 10 + int(num) * 2 // 10
for idx, num in enumerate(reversed(remaining_numbers))]
 
return (sum(nums) + last_digit) % 10 == 0
 
def verify(self) -> bool:
"""Verify a number using Luhn algorithm"""
return self.__checksum()
</syntaxhighlight>
 
== Uses ==
Line 223 ⟶ 122:
* [[Payment card number|Credit card numbers]]
* [[International Mobile Equipment Identity|IMEI numbers]]
* [[CUSIP]] numbers for North American financial instruments
* [[National Provider Identifier|National Provider Identifier numbers]] in the United States
* [[Canada|Canadian]] [[social insurance number]]s
Line 228 ⟶ 128:
* [[South Africa|South African]] ID numbers
* [[South Africa|South African]] Tax reference numbers
* [[Personal identity number (Sweden)| Swedish]] [[nationalPersonal identificationidentity numbers number]]s
* [[Sweden|Swedish]] Corporate Identity Numbers (OrgNr)
* [[Greece|Greek]] Social Security Numbers (ΑΜΚΑ)
Line 239 ⟶ 139:
==References==
<references/>
 
==Notes==
{{notelist}}
 
==External links==
Line 249 ⟶ 152:
[[Category:1954 introductions]]
[[Category:Articles with example pseudocode]]
[[Category:Management cybernetics]]
Retrieved from "https://en.wikipedia.org/wiki/Luhn_algorithm"