Algoritmo Luhn mod N - Luhn mod N algorithm

O algoritmo Luhn mod N é uma extensão do algoritmo Luhn (também conhecido como algoritmo mod 10) que permite trabalhar com sequências de valores em qualquer base . Isso pode ser útil quando um dígito de verificação é necessário para validar uma sequência de identificação composta de letras, uma combinação de letras e dígitos ou qualquer conjunto arbitrário de N caracteres.

Explicação informal

O algoritmo Luhn mod N gera um dígito de verificação (mais precisamente, um caractere de verificação) dentro do mesmo intervalo de caracteres válidos que a string de entrada. Por exemplo, se o algoritmo for aplicado a uma string de letras minúsculas ( a a z ), o caractere de verificação também será uma letra minúscula. Tirando essa distinção, ele se parece muito com o algoritmo original.

A ideia principal por trás da extensão é que o conjunto completo de caracteres de entrada válidos é mapeado para uma lista de pontos de código (ou seja, inteiros sequenciais começando com zero). O algoritmo processa a string de entrada convertendo cada caractere em seu ponto de código associado e, em seguida, executando os cálculos no mod N (onde N é o número de caracteres de entrada válidos). Finalmente, o ponto de código de verificação resultante é mapeado de volta para obter seu caractere de verificação correspondente.

Mapeando caracteres para pontos de código

Inicialmente, um mapeamento entre caracteres de entrada válidos e pontos de código deve ser criado. Por exemplo, considere que os caracteres válidos são as letras minúsculas de a a f . Portanto, um mapeamento adequado seria:

Observe que a ordem dos personagens é completamente irrelevante. Este outro mapeamento também seria aceitável (embora possivelmente mais complicado de implementar):

Também é possível misturar letras e dígitos (e possivelmente até outros caracteres). Por exemplo, este mapeamento seria apropriado para dígitos hexadecimais em minúsculas:

Algoritmo em C #

Supondo que as seguintes funções sejam definidas:

int CodePointFromCharacter(char character) {...}

char CharacterFromCodePoint(int codePoint) {...}

int NumberOfValidInputCharacters() {...}

A função para gerar um caractere de verificação é:

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);
}

E a função para validar uma string (com o caractere de verificação como o último caractere) é:

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);
}

Algoritmo em Java

Supondo que as seguintes funções sejam definidas:

int codePointFromCharacter(char character) {...}

char characterFromCodePoint(int codePoint) {...}

int numberOfValidInputCharacters() {...}

A função para gerar um caractere de verificação é:

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);
}

E a função para validar uma string (com o caractere de verificação como o último caractere) é:

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);
}

Algoritmo em JavaScript

Supondo que as seguintes funções sejam definidas:

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);
}

A função para gerar um caractere de verificação é:

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);
}

E a função para validar uma string (com o caractere de verificação como o último caractere) é:

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);
}

Exemplo

Geração

Considere o conjunto acima de caracteres de entrada válidos e a string de entrada de exemplo abcdef . Para gerar o caractere de verificação, comece com o último caractere na string e mova para a esquerda dobrando todos os outros pontos de código. Os "dígitos" dos pontos de código como escritos na base 6 (uma vez que existem 6 caracteres de entrada válidos) devem então ser somados:

A soma total dos dígitos é 14 (0 + 2 + 2 + 1 + 4 + 5). O número que deve ser adicionado para obter o próximo múltiplo de 6 (neste caso, 18 ) é 4 . Este é o ponto de código de verificação resultante. O caractere de verificação associado é e .

Validação

A string resultante abcdefe pode então ser validada usando um procedimento semelhante:

A soma total dos dígitos é 18 . Como é divisível por 6, o caractere de verificação é válido .

Implementação

O mapeamento de caracteres para pontos de código e vice-versa pode ser implementado de várias maneiras. A abordagem mais simples (semelhante ao algoritmo Luhn original) é usar aritmética de código ASCII. Por exemplo, dado um conjunto de entrada de 0 a 9 , o ponto de código pode ser calculado subtraindo o código ASCII para '0' do código ASCII do caractere desejado. A operação reversa fornecerá o mapeamento reverso. Intervalos adicionais de caracteres podem ser tratados usando declarações condicionais.

Conjuntos não sequenciais podem ser mapeados de ambas as maneiras usando uma instrução switch / case embutida. Uma abordagem mais flexível é usar algo semelhante a uma matriz associativa . Para que isso funcione, um par de matrizes é necessário para fornecer o mapeamento bidirecional.

Uma possibilidade adicional é usar uma matriz de caracteres onde os índices da matriz são os pontos de código associados a cada caractere. O mapeamento do caractere ao ponto de código pode então ser executado com uma pesquisa linear ou binária. Nesse caso, o mapeamento reverso é apenas uma pesquisa de array simples.

Fraqueza

Esta extensão compartilha a mesma fraqueza do algoritmo original, ou seja, não pode detectar a transposição da sequência <first-valid-character> <last-valid-character> para <last-valid-character> <first-valid-character> (ou vice-versa). Isso é equivalente à transposição de 09 para 90 (assumindo um conjunto de caracteres de entrada válidos de 0 a 9 na ordem). Em uma nota positiva, quanto maior o conjunto de caracteres de entrada válidos, menor o impacto da fraqueza.

Veja também

• Número de identificação de títulos internacionais (ISIN)