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

Простая формула контрольной суммы

Алгоритм Луна или формула Луна , также известный как алгоритм « модуль 10» или «модуль 10» , названный в честь его создателя, ученого IBM Ханса Питера Луна , представляет собой простую формулу контрольных цифр , используемую для проверки различных идентификационных номеров.

Он описан в патенте США № 2950048, выданном 23 августа 1960 г. ^[1]

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

Описание

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

1. Если номер уже содержит контрольную цифру, отбросьте эту цифру, чтобы сформировать «полезную нагрузку». Контрольная цифра чаще всего является последней цифрой.
2. С полезной нагрузкой начните с самой правой цифры. Двигаясь влево, удвойте значение каждой второй цифры (включая самую правую цифру).
3. Суммируйте значения полученных цифр.
4. Контрольная цифра вычисляется по формуле , где s — сумма, полученная на шаге 3. Это наименьшее число (возможно, ноль), к которому необходимо прибавить число, кратное 10. Другими допустимыми формулами, дающими то же значение , являются , и . Обратите внимание, что формула не будет работать во всех средах из-за различий в том, как отрицательные числа обрабатываются операцией по модулю . ${\displaystyle (10-(s{\bmod {1}}0)){\bmod {1}}0}$ ${\displaystyle s}$ ${\displaystyle 9-((s+9){\bmod {1}}0)}$ ${\displaystyle (10-s){\bmod {1}}0}$ ${\displaystyle 10\lceil s/10\rceil -s}$ ${\displaystyle (10-s){\bmod {1}}0}$

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

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

Сумма получившихся цифр равна 56.

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

В результате полный номер счета будет выглядеть как 17893729974.

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

1. Отбросьте контрольную цифру (последнюю цифру) номера для проверки. (например, 17893729974 → 1789372997)
2. Вычислите контрольную цифру (см. выше)
3. Сравните полученный результат с исходной контрольной цифрой. Если оба числа совпадают, результат действителен. (например (givenCheckDigit = вычисленнаяCheckDigit) ⇔ (isValidCheckDigit)).

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

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

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

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

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

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

Следующая функция принимает номер карты, включая контрольную цифру, как массив целых чисел и выводит true, если контрольная цифра правильная, и false в противном случае.

функция isValid(cardNumber[1..length]) сумма := 0 четность:= модификация длины 2 для i от 1 до длины, если я mod 2 != четность, тогда сумма := сумма + номер карты[i] elseif cardNumber[i] > 4 , тогда сумма := сумма + 2 * номер карты[i] - 9 еще сумма := сумма + 2 * номер карты[i] end if  end for  return cardNumber[length] == (10 - (sum mod 10)) конечная функция

Реализация кода

С#

bool IsValidLuhn ( в int [ 1 ] цифр )   { интервал check_digit = 0 ;    for ( int i = цифры . Длина - 2 ; я >= 0 ; -- i )           check_digit += (( i & 1 ) равно 0 ) переключатель        { true => цифры [ i ] > 4 ? цифры [ i ] * 2–9 : цифры [ i ] * 2 , _ _               ложь => цифры [ я ]   }; вернуть 10 - ( check_digit % 10 ) == цифры . Последний ();       }

Джава

public static boolean isValidLuhn ( строковый номер ) {      int контрольная сумма = Символ . getNumericValue ( number.charAt ( number.length ( ) - 1 ) ) ; _      целое число = 0 ;    for ( int я знак равно число . длина () - 2 ; я >= 0 ; я -- ) {            интервал сумма = 0 ;    целая цифра = Символ . getNumericValue ( number . charAt ( i ));    if ( i % 2 == число . length () % 2 ) { //справа налево каждая нечетная цифра          цифра = цифра * 2 ;     } сумма = цифра / 10 + цифра % 10 ;         итог += сумма ;   } общая сумма возврата % 10 != 0 ? 10 - всего % 10 == контрольная сумма : контрольная сумма == 0 ;                  }

Использование

Алгоритм Луна используется во множестве систем, в том числе:

• Номера кредитных карт
• номера IMEI
• Национальные идентификационные номера поставщика услуг в США.
• Номера канадского социального страхования
• Израильские идентификационные номера
• Южноафриканские идентификационные номера
• Справочные номера налоговых органов Южной Африки
• Шведские национальные идентификационные номера
• Шведские фирменные номера (OrgNr)
• Номера социального страхования Греции (ΑΜΚΑ)
• ICCID SIM-карт
• Номера заявок на европейские патенты
• Коды опросов, указанные в квитанциях McDonald's , Taco Bell и Tractor Supply Co.
• В номерах отслеживания посылок Почтовой службы США используется модифицированный алгоритм Луна ^[3].

Рекомендации

1. Патент США 2950048A, Лун, Ханс П. , «Компьютер для проверки чисел», опубликовано 23 августа 1960 г. 
2. «Приложение B: Формула Луна для вычисления контрольных цифр по модулю-10 «двойное сложение-двойное»» . Карты удостоверения личности. Идентификация эмитентов. Часть 1. Система нумерации (Стандарт). Международная организация по стандартизации , Международная электротехническая комиссия . Январь 2017 г. ISO/IEC 7812-1 :2017.
3. «Публикация 199: Руководство по внедрению интеллектуального штрих-кода почтового пакета (IMpb) для служб подтверждения и систем электронных платежей» . Почтовая служба США . Проверено 29 ноября 2023 г.

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

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