Алгоритм Луна mod N

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

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

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

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

Ограничение

Алгоритм Луна mod N работает только там, где N делится на 2. Это связано с тем, что существует операция по исправлению значения позиции после удвоения ее значения, которая не работает, когда N не делится на 2. Для приложений, использующих английский алфавит. это не проблема, поскольку строка строчных букв имеет 26 кодовых точек, а добавление десятичных символов добавляет еще 10, сохраняя N , делимое на 2.

Объяснение

На втором этапе Луна удвоенное значение позиции переупаковывается в базу исходной цифры путем сложения отдельных цифр удвоенного значения при записи в базу N. алгоритма Этот шаг приводит к получению четных чисел, если удвоенное значение меньше или равно N если удвоенное значение больше N. , и нечетных чисел , Например, в десятичных приложениях, где N равно 10, исходные значения от 0 до 4 приводят к четным числам, а исходные значения от 5 до 9 — к нечетным числам, эффективно переупаковывая удвоенные значения от 0 до 18 в один отличный результат между 0 и 9.

Если N используется , которое не делится на 2, этот шаг возвращает четные числа для удвоенных значений, больших N , которые невозможно отличить от удвоенных значений, меньших или равных N .

Исход

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

Сопоставление символов с кодовыми точками

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

Характер	а	б	с	д	и	ж
Кодовая точка	0	1	2	3	4	5

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

Характер	с	и	а	ж	б	д
Кодовая точка	0	1	2	3	4	5

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

Характер	0	1	2	3	4	5	6	7	8	9	а	б	с	д	и	ж
Кодовая точка	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

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

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

    /// <summary>
    /// This can be any string of characters.
    /// </summary>
    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];

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

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), следует суммировать:

Характер	а	б	с	д	и	ж
Кодовая точка	0	1	2	3	4	5
Двойной		2		6 (основание 10) 10 (основание 6)		10 (основание 10) 14 (основание 6)
Уменьшать	0	2	2	1 + 0	4	1 + 4
Сумма цифр	0	2	2	1	4	5

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

Валидация

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

Характер	а	б	с	д	и	ж	и
Кодовая точка	0	1	2	3	4	5	4
Двойной		2		6 (основание 10) 10 (основание 6)		10 (основание 10) 14 (основание 6)
Уменьшать	0	2	2	1 + 0	4	1 + 4	4
Сумма цифр	0	2	2	1	4	5	4

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

Выполнение

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

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

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

Слабость

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

См. также

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