Алгоритм Luhn mod N - Luhn mod N algorithm

Алгоритм Лун мод N является расширением к алгоритму Luhn (также известный как моды 10 алгоритма) , что позволяет ему работать с последовательностями значений в любой базе . Это может быть полезно, когда контрольная цифра требуется для подтверждения строки идентификации, состоящей из букв, комбинации букв и цифр или любого произвольного набора из N символов.

Неформальное объяснение

Алгоритм Luhn mod N генерирует контрольную цифру (точнее, контрольный символ) в том же диапазоне допустимых символов, что и входная строка. Например, если алгоритм применяется к строке строчных букв (от a до z ), контрольный символ также будет строчной буквой. Помимо этого различия, он очень похож на исходный алгоритм.

Основная идея расширения состоит в том, что полный набор допустимых входных символов отображается в список кодовых точек (т. Е. Последовательные целые числа, начинающиеся с нуля). Алгоритм обрабатывает входную строку, преобразовывая каждый символ в связанную с ним кодовую точку, а затем выполняет вычисления по модулю N (где N - количество допустимых входных символов). Наконец, результирующая кодовая точка проверки отображается обратно для получения соответствующего проверочного символа.

Отображение символов на кодовые точки

Первоначально необходимо создать соответствие между допустимыми входными символами и кодовыми точками. Например, предположим , что допустимые символы - это строчные буквы от a до f . Следовательно, подходящим отображением будет:

Обратите внимание, что порядок символов совершенно не имеет значения. Это другое сопоставление также будет приемлемым (хотя, возможно, более громоздким для реализации):

Также возможно смешивать буквы и цифры (и, возможно, даже другие символы). Например, это сопоставление подходит для шестнадцатеричных цифр в нижнем регистре:

Алгоритм на C #

Предполагая, что определены следующие функции:

int CodePointFromCharacter(char character) {...}

char CharacterFromCodePoint(int codePoint) {...}

int NumberOfValidInputCharacters() {...}

Функция для генерации контрольного символа:

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

И функция для проверки строки (с контрольным символом в качестве последнего символа):

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

Алгоритм на Java

Предполагая, что определены следующие функции:

int codePointFromCharacter(char character) {...}

char characterFromCodePoint(int codePoint) {...}

int numberOfValidInputCharacters() {...}

Функция для генерации контрольного символа:

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

И функция для проверки строки (с контрольным символом в качестве последнего символа):

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

Алгоритм в JavaScript

Предполагая, что определены следующие функции:

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

Функция для генерации контрольного символа:

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

И функция для проверки строки (с контрольным символом в качестве последнего символа):

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

пример

Поколение

Рассмотрим приведенный выше набор допустимых входных символов и пример входной строки abcdef . Чтобы сгенерировать контрольный символ, начните с последнего символа в строке и двигайтесь влево, удваивая все остальные кодовые точки. Затем следует суммировать "цифры" кодовых точек, записанные в базе 6 (поскольку имеется 6 допустимых входных символов):

Общая сумма цифр 14 (0 + 2 + 2 + 1 + 4 + 5). Чтобы получить следующее кратное 6 (в данном случае 18 ) число, нужно сложить 4 . Это результирующий код проверки. Соответствующий контрольный символ - e .

Проверка

Результирующую строку abcdefe можно затем проверить, используя аналогичную процедуру:

Общая сумма цифр 18 . Так как он делится на 6, проверочный символ действителен .

Реализация

Сопоставление символов с кодовыми точками и обратно может быть реализовано несколькими способами. Самый простой подход (похожий на исходный алгоритм Луна) - использовать арифметику кода ASCII. Например, для входного набора от 0 до 9 кодовая точка может быть вычислена путем вычитания кода ASCII для «0» из кода ASCII желаемого символа. Обратная операция обеспечит обратное отображение. С дополнительными диапазонами символов можно обращаться с помощью условных операторов.

Непоследовательные наборы можно сопоставить в обоих направлениях с помощью жестко запрограммированного оператора switch / case . Более гибкий подход - использовать что-то похожее на ассоциативный массив . Для этого требуется пара массивов для обеспечения двустороннего сопоставления.

Дополнительная возможность заключается в использовании массива символов, где индексы массива являются кодовыми точками, связанными с каждым символом. Преобразование символа в кодовую точку затем может выполняться с помощью линейного или двоичного поиска. В этом случае обратное отображение - это просто поиск в массиве.

Слабость

Это расширение имеет ту же слабость, что и исходный алгоритм, а именно, оно не может обнаружить транспонирование последовательности <first-valid-character> <last-valid-character> в <last-valid-character> <first-valid-character> (или наоборот). Это эквивалентно преобразованию 09 в 90 (при условии набора допустимых входных символов от 0 до 9 в порядке). Положительным моментом является то, что чем больше набор допустимых входных символов, тем меньше влияние слабости.

Смотрите также

• Международный идентификационный номер ценных бумаг (ISIN)