Algoritmo de Luhn mod N - Luhn mod N algorithm

El algoritmo de Luhn mod N es una extensión del algoritmo de Luhn (también conocido como algoritmo mod 10) que le permite trabajar con secuencias de valores en cualquier base . Esto puede resultar útil cuando se requiere un dígito de control para validar una cadena de identificación compuesta por letras, una combinación de letras y dígitos o cualquier conjunto arbitrario de N caracteres.

Explicación informal

El algoritmo Luhn mod N genera un dígito de control (más precisamente, un carácter de control) dentro del mismo rango de caracteres válidos que la cadena de entrada. Por ejemplo, si el algoritmo se aplica a una cadena de letras minúsculas (de la a a la z ), el carácter de verificación también será una letra minúscula. Aparte de esta distinción, se parece mucho al algoritmo original.

La idea principal detrás de la extensión es que el conjunto completo de caracteres de entrada válidos se asigna a una lista de puntos de código (es decir, enteros secuenciales que comienzan con cero). El algoritmo procesa la cadena de entrada convirtiendo cada carácter en su punto de código asociado y luego realizando los cálculos en mod N (donde N es el número de caracteres de entrada válidos). Finalmente, el punto de código de verificación resultante se vuelve a asignar para obtener su carácter de verificación correspondiente.

Asignación de caracteres a puntos de código

Inicialmente, se debe crear un mapeo entre caracteres de entrada válidos y puntos de código. Por ejemplo, consideran que los caracteres válidos son las letras minúsculas de una a f . Por tanto, un mapeo adecuado sería:

Tenga en cuenta que el orden de los personajes es completamente irrelevante. Este otro mapeo también sería aceptable (aunque posiblemente más engorroso de implementar):

También es posible mezclar letras y dígitos (y posiblemente incluso otros caracteres). Por ejemplo, este mapeo sería apropiado para dígitos hexadecimales en minúsculas:

Algoritmo en C #

Suponiendo que se definan las siguientes funciones:

int CodePointFromCharacter(char character) {...}

char CharacterFromCodePoint(int codePoint) {...}

int NumberOfValidInputCharacters() {...}

La función para generar un carácter de verificación es:

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

Y la función para validar una cadena (con el carácter de verificación como último carácter) es:

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 en Java

Suponiendo que se definan las siguientes funciones:

int codePointFromCharacter(char character) {...}

char characterFromCodePoint(int codePoint) {...}

int numberOfValidInputCharacters() {...}

La función para generar un carácter de verificación es:

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

Y la función para validar una cadena (con el carácter de verificación como último carácter) es:

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 en JavaScript

Suponiendo que se definan las siguientes funciones:

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

La función para generar un carácter de verificación es:

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

Y la función para validar una cadena (con el carácter de verificación como último carácter) es:

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

Ejemplo

Generacion

Considere el conjunto anterior de caracteres de entrada válidos y la cadena de entrada de ejemplo abcdef . Para generar el carácter de verificación, comience con el último carácter de la cadena y muévase hacia la izquierda doblando cada dos puntos de código. Los "dígitos" de los puntos de código tal como están escritos en la base 6 (ya que hay 6 caracteres de entrada válidos) deben luego resumirse:

La suma total de dígitos es 14 (0 + 2 + 2 + 1 + 4 + 5). El número que se debe sumar para obtener el siguiente múltiplo de 6 (en este caso, 18 ) es 4 . Este es el punto de código de verificación resultante. El carácter de verificación asociado es e .

Validación

La cadena resultante abcdefe se puede validar mediante un procedimiento similar:

La suma total de dígitos es 18 . Dado que es divisible por 6, el carácter de verificación es válido .

Implementación

El mapeo de caracteres a puntos de código y viceversa se puede implementar de varias formas. El enfoque más simple (similar al algoritmo de Luhn original) es usar aritmética de código ASCII. Por ejemplo, dado un conjunto de entrada de 0 a 9 , el punto de código se puede calcular restando el código ASCII para '0' del código ASCII del carácter deseado. La operación inversa proporcionará el mapeo inverso. Se pueden tratar rangos adicionales de caracteres mediante el uso de declaraciones condicionales.

Los conjuntos no secuenciales se pueden mapear en ambos sentidos utilizando una declaración de caso / conmutador codificada . Un enfoque más flexible es usar algo similar a una matriz asociativa . Para que esto funcione, se requieren un par de matrices para proporcionar el mapeo bidireccional.

Una posibilidad adicional es utilizar una matriz de caracteres donde los índices de la matriz son los puntos de código asociados con cada carácter. El mapeo de carácter a punto de código se puede realizar con una búsqueda lineal o binaria. En este caso, el mapeo inverso es solo una simple búsqueda de matriz.

Debilidad

Esta extensión comparte la misma debilidad que el algoritmo original, es decir, no puede detectar la transposición de la secuencia <primero- carácter- válido> <último- carácter- válido> a <último- carácter- válido> <primer carácter- válido> (o viceversa). Esto es equivalente a la transposición de 09 a 90 (asumiendo un conjunto de caracteres de entrada válidos de 0 a 9 en orden). En una nota positiva, cuanto mayor sea el conjunto de caracteres de entrada válidos, menor será el impacto de la debilidad.

Ver también

• Número de identificación internacional de valores (ISIN)