Лун алгоритм или формула Лун , также известный как « модуль 10» или « по модулю 10» алгоритм , названный в честь его создателя, IBM ученый Ханс Петер Лун , это простая контрольная формула используется для проверки различных идентификационных номеров, таких как кредит номера карт , номер IMEI , Национальный Provider номер идентификаторы в США, канадское социальное страхование числа , израильские идентификационные номера, южноафриканские идентификационные номера, греческие номера социального страхования (ΑΜΚΑ), и коды опроса появляются наКвитанции McDonald's , Taco Bell и Tractor Supply Co. Он описан в патенте США № 2,950,048 , поданном 6 января 1954 г. и выданном 23 августа 1960 г.
Алгоритм является общественным достоянием и широко используется сегодня. Это указано в ISO / IEC 7812-1 . [1] Он не предназначен для использования в качестве криптографически безопасной хеш-функции ; он был разработан для защиты от случайных ошибок, а не от злонамеренных атак. Большинство кредитных карт и многие государственные идентификационные номера используют алгоритм как простой метод отличия действительных номеров от ошибочно набранных или иным образом неверных.
Описание [ править ]
Формула сравнивает число с включенной контрольной цифрой , которая обычно добавляется к частичному номеру счета для генерации полного номера счета. Этот номер должен пройти следующий тест:
- Начиная с самой правой цифры (исключая контрольную цифру) и двигаясь влево, удвойте значение каждой второй цифры. Контрольная цифра не удваивается и не включается в этот расчет; первая удвоенная цифра - это цифра, расположенная сразу слева от контрольной цифры. Если результат этой операции удвоения больше 9 (например, 8 × 2 = 16), тогда сложите цифры результата (например, 16: 1 + 6 = 7, 18: 1 + 8 = 9) или, что то же самое, , вычтите 9 из результата (например, 16: 16 - 9 = 7, 18: 18 - 9 = 9).
- Возьмите сумму всех цифр (включая контрольную).
- Если сумма по модулю 10 равна 0 (если сумма заканчивается нулем), то число действительно согласно формуле Луна; в противном случае это недействительно.
Пример вычисления контрольной цифры [ править ]
Предположим, что для номера счета «7992739871» будет добавлена контрольная цифра, которая будет иметь форму 7992739871x:
| 7 | 9 | 9 | 2 | 7 | 3 | 9 | 8 | 7 | 1 | Икс | |
| Удвойте друг друга | 7 | 18 | 9 | 4 | 7 | 6 | 9 | 16 | 7 | 2 | Икс |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Сумма цифр | 7 | 9 | 9 | 4 | 7 | 6 | 9 | 7 | 7 | 2 | Икс |
Сумма всех цифр в третьей строке, сумма цифр суммы, равна 67.
Контрольная цифра (x) получается путем вычисления суммы цифр суммы, а затем вычисления 9-кратного значения по модулю 10 (в форме уравнения ((67 × 9) по модулю 10)). В виде алгоритма:
- Вычислите сумму цифр суммы (67).
- Умножьте на 9 (603).
- 603 mod 10 - это контрольная цифра 3. Таким образом, x = 3 .
(Альтернативный метод) Контрольная цифра (x) получается путем вычисления суммы других цифр (третья строка), а затем вычитания цифры единиц из 10 (67 => цифра единиц 7; 10-7 = контрольная цифра 3). В виде алгоритма:
- Вычислите сумму цифр суммы (67).
- Возьмите цифру единиц (7).
- Вычтите цифру единиц из 10.
- Результат (3) - это контрольная цифра. Если сумма цифр оканчивается на 0, то 0 является контрольной цифрой.
Это делает полный номер счета 79927398713.
Пример проверки контрольной цифры [ править ]
Каждый из номеров 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 можно проверить следующим образом.
- Удваивайте каждую вторую цифру, начиная с самого правого: (1 × 2) = 2, (8 × 2) = 16, (3 × 2) = 6, (2 × 2) = 4, (9 × 2) = 18
- Суммируйте все отдельные цифры (цифры в скобках - это произведения из шага 1): x (контрольная цифра) + (2) + 7 + (1 + 6) + 9 + (6) + 7 + (4) + 9 + (1 + 8) + 7 = х + 67.
- Если сумма кратна 10, возможно, номер счета действителен. Обратите внимание, что 3 - единственная допустимая цифра, которая дает сумму (70), кратную 10.
- Таким образом, все эти номера счетов недействительны, за исключением, возможно, 79927398713, у которого есть правильная контрольная цифра.
В качестве альтернативы вы можете использовать тот же алгоритм создания контрольной суммы, игнорируя уже имеющуюся контрольную сумму, как если бы она еще не была рассчитана. Затем вычислите контрольную сумму и сравните эту рассчитанную контрольную сумму с исходной контрольной суммой, включенной в номер кредитной карты. Если включенная контрольная сумма совпадает с рассчитанной контрольной суммой, то число действительное.
Сильные и слабые стороны [ править ]
Алгоритм Луна обнаружит любую ошибку, связанную с одной цифрой, а также почти все перестановки соседних цифр. Однако он не обнаружит транспонирование двузначной последовательности 09 в 90 (или наоборот). Он обнаружит большинство возможных двойных ошибок (он не обнаружит 22 ↔ 55 , 33 ↔ 66 или 44 ↔ 77 ).
Другие, более сложные алгоритмы проверки цифр (например, Verhoeff алгоритм и алгоритм Дамм ) могут обнаружить больше ошибок транскрипции. Лун мод N алгоритм является расширением , которое поддерживает нечисловые строки.
Поскольку алгоритм работает с цифрами справа налево, а нулевые цифры влияют на результат, только если они вызывают сдвиг позиции, заполнение нулями начала строки чисел не влияет на вычисления. Следовательно, системы, которые дополняют определенное количество цифр (например, путем преобразования 1234 в 0001234), могут выполнять проверку Luhn до или после заполнения и достигать того же результата.
Добавление 0 к нечетным числам дает возможность обрабатывать число слева направо, а не справа налево, удваивая нечетные цифры.
Алгоритм появился в патенте США [2] на портативное механическое устройство для вычисления контрольной суммы. Следовательно, требовалось, чтобы это было достаточно просто. Устройство взяло мод 10 сум механическим способом. Эти замены цифры , то есть, результаты двойной и сокращения процедуры, не были получены механическим способом . Скорее, цифры были отмечены на корпусе машины в порядке их перестановки.
Реализация псевдокода [ править ]
функция checkLuhn (строка purportedCC) { int sum: = integer (purportedCC [длина (purportedCC) -1]) int nDigits: = длина (purportedCC) int четность: = nDigits модуль 2 для i от 0 до nDigits - 2 { int digit: = integer (purportedCC [i]) если i модуль 2 = четность цифра: = цифра × 2 если цифра> 9 цифра: = цифра - 9 сумма: = сумма + цифра } возврат (модуль суммы 10) = 0}Использование [ править ]
Помимо номеров кредитных карт, этот алгоритм также используется для вычисления контрольной цифры на номерах SIM-карт.
Ссылки [ править ]
Внешние ссылки [ править ]
- Реализация на 88 языках в проекте Rosetta Code
