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

Лун алгоритм или формула Лун , также известный как « модуль 10» или « по модулю 10» алгоритм , названный в честь его создателя, IBM ученый Ханс Петер Лун , это простая контрольная формула используется для проверки различных идентификационных номеров, таких как кредит номера карт , номер IMEI , номер идентификатора национального провайдера в Соединенных Штатах, канадское социальное страхование число , израильские идентификационные номера, южноафриканские идентификационные номера, Swedish национальный идентификационные номера ,Шведские Фирменный стиль Число (OrgNr), греческие номера социального страхования (ΑΜΚΑ), номер SIM - карта и коды опроса , появляющиеся на Макдональдс , Taco Bell , и Tractor Supply Co. квитанциях. Он описан в патенте США № 2,950,048, выданном 23 августа 1960 г. ^[1]

Алгоритм является общественным достоянием и широко используется сегодня. Это указано в ISO / IEC 7812-1 . ^[2] Он не предназначен для использования в качестве криптографически безопасной хеш-функции ; он был разработан для защиты от случайных ошибок, а не от злонамеренных атак. Большинство кредитных карт и многие государственные идентификационные номера используют алгоритм в качестве простого метода отличия действительных номеров от набранных с ошибками или иным образом неправильных номеров.

Описание

Контрольная цифра вычисляется следующим образом:

1. Возьмите исходное число и, начиная с крайней правой цифры, двигаясь влево, удвойте значение каждой второй цифры (включая крайнюю правую цифру).
2. Замените полученное значение в каждой позиции суммой цифр значения этой позиции.
3. Суммировать полученные значения со всех позиций ( ы ).
4. Расчетная контрольная цифра равна .${\ displaystyle 10-s \ operatorname {mod} 10}$

Пример вычисления контрольной цифры

Рассмотрим пример номера счета «7992739871» (только «полезная нагрузка», контрольная цифра еще не включена):

Сумма полученных цифр 67.

Контрольная цифра равна .${\displaystyle 10-67\operatorname {mod} 10=3}$

Это делает полный номер счета 79927398713.

Пример проверки контрольной цифры

Просто обрежьте контрольную цифру (последнюю цифру) числа для подтверждения. 79927398713 -> 7992739871 Вычислите контрольную цифру (см. Выше) (3) и сравните свой результат с контрольной цифрой, которую вы отсекли (3 = 3). Если они совпадают, то тест пройден.

Сильные и слабые стороны

Алгоритм Луна обнаружит любую ошибку одной цифры, а также почти все транспозиции соседних цифр. Однако он не обнаружит перестановку двузначной последовательности 09 на 90 (или наоборот). Он обнаружит большинство возможных двойных ошибок (он не обнаружит 22 ↔ 55 , 33 ↔ 66 или 44 ↔ 77 ).

Другие, более сложные алгоритмы проверки цифр (например, Verhoeff алгоритм и алгоритм Дамм ) могут обнаружить больше ошибок транскрипции. Лун мод N алгоритм является расширением , которое поддерживает нечисловые строки.

Поскольку алгоритм работает с цифрами справа налево, а нулевые цифры влияют на результат только в том случае, если они вызывают сдвиг позиции, заполнение нулями начала строки чисел не влияет на вычисления. Следовательно, системы, которые дополняют определенное количество цифр (например, путем преобразования 1234 в 0001234), могут выполнять проверку Luhn до или после заполнения и достигать того же результата.

Алгоритм появился в патенте США ^[1] на портативное механическое устройство для вычисления контрольной суммы. Следовательно, требовалось, чтобы это было достаточно просто. Устройство взяло мод 10 сум механическим способом. Эти замены цифры , то есть, результаты двойной и сокращения процедуры, не были получены механическим способом . Скорее, цифры были отмечены на корпусе машины в порядке их перестановки.

Реализация псевдокода

функция checkLuhn (строка purportedCC) { int nDigits: = длина (purportedCC) int sum: = integer (purportedCC [nDigits-1]) int четность: = (nDigits-1) модуль 2 для i от 0 до nDigits - 2 { int digit: = integer (purportedCC [i]) если i модуль 2 = четность цифра: = цифра × 2 если цифра> 9 цифра: = цифра - 9 сумма: = сумма + цифра } возврат (модуль суммы 10) = 0
}

использованная литература

внешние ссылки

• Реализация на 88 языках в проекте Rosetta Code