Luhn mod N algorithm
≈ 8 min read
Names in other languages
- EnglishLuhn mod N algorithm
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 values in any even-numbered base. This can be useful when a check digit is required to validate an identification string composed of letters, a combination of letters and digits or any arbitrary set of characters where is divisible by 2.
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 values in any even-numbered base. This can be useful when a check digit is required to validate an identification string composed of letters, a combination of letters and digits or any arbitrary set of characters where is divisible by 2.
Original algorithm (Luhn mod 10)
The original Luhn algorithm was designed by Hans Peter Luhn and patented in 1960 (as a physical device for implementing the algorithm). It is a check digit algorithm that is intended to catch most common input errors by checking the algorithm's calculation of the digits of an identification number against the final ("check") digit. One particularly common use of the Luhn algorithm is in credit cards; the final digit of a 16-digit credit card number is the output of the Luhn algorithm applied to the first 15 digits. Government ID numbers, bank account numbers, ISBN numbers and many other identification numbers use the Luhn algorithm or a small modification of it. The original Luhn algorithm is a special case of the Luhn mod algorithm, where equals 10. It takes in a string of digits (omitting the final digit), reverses the string, multiplies every other digit by two, then sums all of them. The final digit of this sum should be the same as the final digit of the string. (For a full example of this calculation, see Luhn algorithm#Description.) The goal of the Luhn algorithm is to detect common input errors when entering a string of digits into a computer. It catches all substitution errors, where one digit is accidentally replaced by another, as well as most transposition errors, with 90 vs. 09 being the sole exception. Although it is a hash function, it is not intended to be cryptographically secure, nor to detect malicious errors or fraud.
Extending to mod N
The original Luhn algorithm is called the "mod 10" algorithm because it performs modular arithmetic on a 10-digit system. The check digit is generated by summing up the Luhn algorithm and taking the result modulo 10, which is equivalent to the remainder left over when dividing by 10, or the "ones" digit of the number. The same basic idea can be applied to an arbitrary system of N ordered characters. The Luhn mod N algorithm generates a check digit (more precisely, a check character) within the same range of valid characters as the input string. For example, if the algorithm is applied to a string of lower-case letters (a to z), the check character will also be a lower-case letter. Apart from this distinction, it resembles very closely the original algorithm. The main idea behind the extension is that the full set of valid input characters is mapped to a list of code-points (i.e., sequential integers beginning with zero). The algorithm processes the input string by converting each character to its associated code-point and then performing the computations in mod N (where is the number of valid input characters). Finally, the resulting check code-point is mapped back to obtain its corresponding check character. /// /// This can be any string of characters. /// private const string CodePoints = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; private int NumberOfValidInputCharacters() => CodePoints.Length; private int CodePointFromCharacter(char character) => CodePoints.IndexOf(character); private char CharacterFromCodePoint(int codePoint) => CodePoints[codePoint]; The function to generate a check character is: char GenerateCheckCharacter(string input) { int factor = 2; int sum = 0; int n = NumberOfValidInputCharacters(); // Starting from the right and working leftwards is easier since // the initial "factor" will always be "2". for (int i = input.Length - 1; i >= 0; i--) { int codePoint = CodePointFromCharacter(input[i]); int addend = factor * codePoint; // Alternate the "factor" that each "codePoint" is multiplied by factor = (factor == 2) ? 1 : 2; // Sum the digits of the "addend" as expressed in base "n" addend = IntegerValue(addend / n) + (addend % n); sum += addend; } // Calculate the number that must be added to the "sum" // to make it divisible by "n". int remainder = sum % n; int checkCodePoint = (n - remainder) % n; return CharacterFromCodePoint(checkCodePoint); } And the function to validate a string (with the check character as the last character) is: bool ValidateCheckCharacter(string input) { int factor = 1; int sum = 0; int n = NumberOfValidInputCharacters(); // Starting from the right, work leftwards // Now, the initial "factor" will always be "1" // since the last character is the check character. for (int i = input.Length - 1; i >= 0; i--) { int codePoint = CodePointFromCharacter(input[i]); int addend = factor * codePoint; // Alternate the "factor" that each "codePoint" is multiplied by factor = (factor == 2) ? 1 : 2; // Sum the digits of the "addend" as expressed in base "n" addend = IntegerValue(addend / n) + (addend % n); sum += addend; } int remainder = sum % n; return (remainder == 0); } int codePointFromCharacter(char character) {...} char characterFromCodePoint(int codePoint) {...} int numberOfValidInputCharacters() {...} The function to generate a check character is: char generateCheckCharacter(String input) { int factor = 2; int sum = 0; int n = numberOfValidInputCharacters(); // Starting from the right and working leftwards is easier since // the initial "factor" will always be "2". for (int i = input.length() - 1; i >= 0; i--) { int codePoint = codePointFromCharacter(input.charAt(i)); int addend = factor * codePoint; // Alternate the "factor" that each "codePoint" is multiplied by factor = (factor == 2) ? 1 : 2; // Sum the digits of the "addend" as expressed in base "n" addend = (addend / n) + (addend % n); sum += addend; } // Calculate the number that must be added to the "sum" // to make it divisible by "n". int remainder = sum % n; int checkCodePoint = (n - remainder) % n; return characterFromCodePoint(checkCodePoint); } And the function to validate a string (with the check character as the last character) is: boolean validateCheckCharacter(String input) { int factor = 1; int sum = 0; int n = numberOfValidInputCharacters(); // Starting from the right, work leftwards // Now, the initial "factor" will always be "1" // since the last character is the check character. for (int i = input.length() - 1; i >= 0; i--) { int codePoint = codePointFromCharacter(input.charAt(i)); int addend = factor * codePoint; // Alternate the "factor" that each "codePoint" is multiplied by factor = (factor == 2) ? 1 : 2; // Sum the digits of the "addend" as expressed in base "n" addend = (addend / n) + (addend % n); sum += addend; } int remainder = sum % n; return (remainder == 0); } const codePoints = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //This can be any string of permitted characters function numberOfValidInputCharacters() { return codePoints.length; } function codePointFromCharacter(character) { return codePoints.indexOf(character); } function characterFromCodePoint(codePoint) { return codePoints.charAt(codePoint); } The function to generate a check character is: function generateCheckCharacter(input) { let factor = 2; let sum = 0; let n = numberOfValidInputCharacters(); // Starting from the right and working leftwards is easier since // the initial "factor" will always be "2". for (let i = input.length - 1; i >= 0; i--) { let codePoint = codePointFromCharacter(input.charAt(i)); let addend = factor * codePoint; // Alternate the "factor" that each "codePoint" is multiplied by factor = (factor == 2) ? 1 : 2; // Sum the digits of the "addend" as expressed in base "n" addend = (Math.floor(addend / n)) + (addend % n); sum += addend; } // Calculate the number that must be added to the "sum" // to make it divisible by "n". let remainder = sum % n; let checkCodePoint = (n - remainder) % n; return characterFromCodePoint(checkCodePoint); } And the function to validate a string (with the check character as the last character) is: function validateCheckCharacter(input) { let factor = 1; let sum = 0; let n = numberOfValidInputCharacters(); // Starting from the right, work leftwards // Now, the initial "factor" will always be "1" // since the last character is the check character. for (let i = input.length - 1; i >= 0; i--) { let codePoint = codePointFromCharacter(input.charAt(i)); let addend = factor * codePoint; // Alternate the "factor" that each "codePoint" is multiplied by factor = (factor == 2) ? 1 : 2; // Sum the digits of the "addend" as expressed in base "n" addend = (Math.floor(addend / n)) + (addend % n); sum += addend; } let remainder = sum % n; return (remainder
0); }
References==
Text derived from https://en.wikipedia.org/w/index.php?oldid=1351189129 under CC BY-SA 4.0; modifications have been made.