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

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

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

СОДЕРЖАНИЕ

• 1 Описание
  • 1.1 Пример вычисления контрольной цифры
  • 1.2 Пример проверки контрольной цифры
• 2 сильные и слабые стороны
• 3 Реализация псевдокода
• 4 ссылки
• 5 Внешние ссылки

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

function checkLuhn(string purportedCC) { int nDigits := length(purportedCC) int sum := integer(purportedCC[nDigits-1]) int parity := (nDigits-1) modulus 2 for i from 0 to nDigits - 2 { int digit := integer(purportedCC[i]) if i modulus 2 = parity digit := digit × 2 if digit gt; 9 digit := digit - 9 sum := sum + digit } return (sum modulus 10) = 0 }

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

1. ^ ^{a b} Патент США 2950048A, Luhn, Hans P., «Компьютер для проверки чисел», опубликован 23 августа 1960 г. 
2. ^ "Приложение B: Формула Луна для вычисления модуля-10" двойное добавление-двойное "контрольные цифры". Идентификационные карты - Идентификация эмитентов - Часть 1: Система нумерации (Стандарт). Международная организация по стандартизации, Международная электротехническая комиссия. Январь 2017. ISO / IEC 7812-1 : 2017.

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

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