Luhn algorithm

Luhn algorithm

The Luhn algorithm or Luhn formula, also known as the "modulus 10" or "mod 10" algorithm, is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers, IMEI numbers, National Provider Identifier numbers in US and Canadian Social Insurance Numbers. It was created by IBM scientist Hans Peter Luhn and described in U.S. Patent No. 2,950,048, filed on January 6, 1954, and granted on August 23, 1960.

The algorithm is in the public domain and is in wide use today. It is specified in ISO/IEC 7812-1.[1] It is not intended to be a 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 collections of random digits.

Contents

Strengths and weaknesses

The Luhn algorithm will detect any single-digit error, as well as almost all transpositions of adjacent digits. It will not, however, detect transposition of the two-digit sequence 09 to 90 (or vice versa). It will detect 7 of the 10 possible twin errors (it will not detect 2255, 3366 or 4477).

Other, more complex check-digit algorithms (such as the Verhoeff algorithm) can detect more transcription errors. The Luhn mod N algorithm is an extension that supports non-numerical strings.

Because the algorithm operates on the digits in a right-to-left manner and zero digits affect the result only if they cause shift in position, zero-padding the beginning of a string of numbers does not affect the calculation. Therefore, systems that pad to a specific number of digits by converting 1234 to 0001234 (for instance) can perform Luhn validation before or after the padding and achieve the same result.

The algorithm appeared in a US Patent for a hand-held, mechanical device for computing the checksum. It was therefore required to be rather simple. The device took the mod 10 sum by mechanical means. The substitution digits, that is, the results of the double and reduce procedure, were not produced mechanically. Rather, the digits were marked in their permuted order on the body of the machine.

Informal explanation

The formula verifies a number against its included check digit, which is usually appended to a partial account number to generate the full account number. This account number must pass the following test:

  1. Counting from the check digit, which is the rightmost, and moving left, double the value of every second digit.
  2. Sum the digits of the products (e.g., 10 = 1 + 0 = 1, 14 = 1 + 4 = 5) together with the undoubled digits from the original number.
  3. If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.

Assume an example of an account number "7992739871" that will have a check digit added, making it of the form 7992739871x:

Account number 7 9 9 2 7 3 9 8 7 1 x
Double every other 7 18 9 4 7 6 9 16 7 2 x
Sum of digits 7 9 9 4 7 6 9 7 7 2 =67

The check digit (x) is obtained by computing the sum of digits modulo 10 and then computing 10 less that value modulo 10 (so that's: ((10 - (67 mod 10)) mod 10)). In layman's terms:

  1. Compute the sum of the digits (67).
  2. Divide by 10, and hold on to the remainder (7).
  3. Compute 10 minus the remainder from the previous step (3).
  4. The result is your check digit. If the answer is "10", you use 0. (shortcut for computing decimal modulus)

This, makes the full account number read 79927398713.

The account number 79927398713 in turn is validated as follows:

  1. Double every second digit, from the rightmost: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
  2. Sum all the individual digits (digits in parentheses are the products from Step 1): 3 + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 7 = 70
  3. Take the sum modulo 10: 70 mod 10 = 0; the account number is possibly valid.

Note: because modulo's properties, you can apply the modulo operation as you add each digit, so you only have to store the last digit in your head. So in this example, instead of counting up to 70, you can track the remainder as you add the digits (and you end up at 0 instead of 70). So your running count becomes: 3, 5, 2, 3, 9, 8, 4, 1, 5, 4, 5, 3, 0.

Implementation of standard Mod 10

Verification of the check digit

In Python:

def is_luhn_valid(cc):
    num = map(int, str(cc))
    return sum(num[::-2] + [sum(divmod(d * 2, 10)) for d in num[-2::-2]]) % 10 == 0

Calculation of the check digit

The above implementations check the validity of an input with a check digit. Calculating the check digit requires only a slight adaptation of the algorithm—namely:

  1. Switch the odd / even multiplication.
  2. If the (sum mod 10) == 0, then the check digit is 0
  3. Else, the check digit = 10 - (sum mod 10)

In Python:

def calculate_luhn(cc):
    num = map(int, str(cc))
    check_digit = 10 - sum(num[-2::-2] + [sum(divmod(d * 2, 10)) for d in num[::-2]]) % 10
    return 0 if check_digit == 10 else check_digit

Other implementations

See also

References

  1. ^ ISO/IEC 7812-1:2006 Identification cards -- Identification of issuers -- Part 1: Numbering system

Wikimedia Foundation. 2010.

См. также в других словарях:

  • Luhn mod N algorithm — The Luhn mod N algorithm is an extension to the Luhn algorithm (also known as mod 10 algorithm) that allows it to work with sequences of non numeric characters. This can be useful when a check digit is required to validate an identification… …   Wikipedia

  • Luhn-Formel — Der Luhn Algorithmus oder die Luhn Formel, auch bekannt als „Modulo 10“ oder „mod 10“ Algorithmus, wurde in den 1960er Jahren von Hans Peter Luhn als eine Methode der Überprüfung von Identifikationsnummern entwickelt. Er ist eine simple… …   Deutsch Wikipedia

  • Verhoeff algorithm — The Verhoeff algorithm, a checksum formula for error detection first published in 1969, was developed by Dutch mathematician Jacobus Verhoeff (born 1927). Like the more widely known Luhn algorithm, it works with strings of decimal digits of any… …   Wikipedia

  • Hans Peter Luhn — (July 1, 1896 ndash; August 19, 1964) was a computer scientist for IBM, and creator of the Luhn algorithm and KWIC (Key Words In Context) indexing. He was awarded over 80 patents.Hans Peter Luhn was born in Barmen, Germany (now part of Wuppertal) …   Wikipedia

  • Bank card number — A bank card number is the primary account number found on credit cards and bank cards. It has a certain amount of internal structure and shares a common numbering scheme. Credit card numbers are a special case of ISO/IEC 7812 bank card numbers.… …   Wikipedia

  • Error detection and correction — In mathematics, computer science, telecommunication, and information theory, error detection and correction has great practical importance in maintaining data (information) integrity across noisy channels and less than reliable storage… …   Wikipedia

  • Check digit — A check digit is a form of redundancy check used for error detection, the decimal equivalent of a binary checksum. It consists of a single digit computed from the other digits in the message. With a check digit, one can detect simple errors in… …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of algebraic coding theory topics — This is a list of algebraic coding theory topics. ARQ[disambiguation needed  ] Adler 32 BCH code BCJR algorithm Berger code Berlekamp Massey algo …   Wikipedia

  • MSI Barcode — for the number 1234567 with Mod 10 check digit MSI (also known as Modified Plessey) is a barcode symbology developed by the MSI Data Corporation, based on the original Plessey Code symbology. It is a continuous symbology that is not self checking …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»