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

Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: "Алгоритм Луна по модулю N"  – Новости  · газеты  · книги  · ученый  · JSTOR (Май 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

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

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

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

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

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

int CodePointFromCharacter(char персонаж) {...}char CharacterFromCodePoint(int codePoint) {...}int NumberOfValidInputCharacters() {...}

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

char GenerateCheckCharacter(нить Вход){    int фактор = 2;    int сумма = 0;    int п = NumberOfValidInputCharacters();    // Начать справа и работать влево проще, так как     // начальный «коэффициент» всегда будет «2».    за (int я = Вход.Длина - 1; я >= 0; я--)    {        int codePoint = CodePointFromCharacter(Вход[я]);        int добавить = фактор * codePoint;        // Меняем "коэффициент", на который умножается каждое "codePoint"        фактор = (фактор == 2) ? 1 : 2;        // Суммируем цифры «слагаемого», выраженные в базе «n»        добавить = IntegerValue(добавить / п) + (добавить % п);        сумма += добавить;    }    // Вычислить число, которое нужно добавить к «сумме»     // чтобы оно делилось на "n".    int остаток = сумма % п;    int checkCodePoint = (п - остаток) % п;    возвращаться CharacterFromCodePoint(checkCodePoint);}

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

bool ValidateCheckCharacter(нить Вход){    int фактор = 1;    int сумма = 0;    int п = NumberOfValidInputCharacters();    // Начиная справа, работаем влево    // Теперь начальный "коэффициент" всегда будет "1"     // поскольку последний символ является контрольным.    за (int я = Вход.Длина - 1; я >= 0; я--)    {        int codePoint = CodePointFromCharacter(Вход[я]);        int добавить = фактор * codePoint;        // Альтернативный "коэффициент", на который умножается каждое "codePoint"        фактор = (фактор == 2) ? 1 : 2;        // Суммируем цифры «слагаемого», выраженные в базе «n»        добавить = IntegerValue(добавить / п) + (добавить % п);        сумма += добавить;    }    int остаток = сумма % п;    возвращаться (остаток == 0);}

Алгоритм на Java

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

int codePointFromCharacter(char персонаж) {...}char characterFromCodePoint(int codePoint) {...}int numberOfValidInputCharacters() {...}

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

char generateCheckCharacter(Нить Вход) {    int фактор = 2;    int сумма = 0;    int п = numberOfValidInputCharacters();    // Начать справа и работать влево проще, так как    // начальный «коэффициент» всегда будет «2».    за (int я = Вход.длина() - 1; я >= 0; я--) {        int codePoint = codePointFromCharacter(Вход.диаграмма(я));        int добавить = фактор * codePoint;        // Альтернативный "коэффициент", на который умножается каждое "codePoint"        фактор = (фактор == 2) ? 1 : 2;        // Суммируем цифры «слагаемого», выраженные в базе «n»        добавить = (добавить / п) + (добавить % п);        сумма += добавить;    }    // Вычислить число, которое нужно добавить к «сумме»    // чтобы оно делилось на "n".    int остаток = сумма % п;    int checkCodePoint = (п - остаток) % п;    возвращаться characterFromCodePoint(checkCodePoint);}

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

логический validateCheckCharacter(Нить Вход) {    int фактор = 1;    int сумма = 0;    int п = numberOfValidInputCharacters();    // Начиная справа, работаем влево    // Теперь начальный "коэффициент" всегда будет "1"    // поскольку последний символ является контрольным.    за (int я = Вход.длина() - 1; я >= 0; я--) {        int codePoint = codePointFromCharacter(Вход.диаграмма(я));        int добавить = фактор * codePoint;        // Альтернативный "коэффициент", на который умножается каждое "codePoint"        фактор = (фактор == 2) ? 1 : 2;        // Суммируем цифры «слагаемого», выраженные в базе «n»        добавить = (добавить / п) + (добавить % п);        сумма += добавить;    }    int остаток = сумма % п;    возвращаться (остаток == 0);}

Пример

Поколение

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

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

Проверка

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

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

Выполнение

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

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

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

Слабое место

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

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

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