Алгоритм Луна
Алгоритм Лу́на (англ. Luhn algorithm) — алгоритм вычисления контрольной цифры номера пластиковых карт в соответствии со стандартом ISO/IEC 7812. Не является криптографическим средством, предназначение алгоритма в первую очередь — выявление ошибок, вызванных непреднамеренным искажением данных (например, при ручном вводе номера карты, при приёме данных о номере социального страхования по телефону). Позволяет лишь с некоторой степенью достоверности судить об отсутствии ошибок в блоке цифр, но не даёт возможности локализации и коррекции обнаруженной неточности.
Алгоритм разработан сотрудником фирмы IBM Гансом Питером Луном, описан в США в 1954 году, патент получен в 1960 году.
Наиболее распространённые применения для подсчёта контрольной цифры:
- Номера всех банковских карт
- Номера некоторых дисконтных карт
- Коды социального страхования
- IMEI-коды
- MEID (модифицированный алгоритм)
В настоящее время содержание алгоритма является публичным достоянием.
Содержание |
[править] Достоинства и недостатки
В силу простоты реализации, алгоритм отнимает минимум вычислительных мощностей; в ряде случаев при наличии навыка расчёт может быть произведён «в уме». В то же время, алгоритм Луна позволяет только выявить ошибки в блоках данных, и то не все. Искажение одной цифры — обнаруживается. Обнаруживаются практически все парные перестановки подряд идущих цифр (за исключением 09 ↔ 90). Не могут быть обнаружены некоторые искажения двух подряд идущих цифр, а именно 22 ↔ 55, 33 ↔ 66 и 44 ↔ 77. Алгоритм не даёт информации о месте и характере возникшей ошибки.
Алгоритм может применяться для последовательностей цифр любой длины, однако при этом следует иметь в виду, что при достаточно длинных числах вероятно появление одновременно нескольких искажений данных; некоторые из таких ошибок могут привести к ошибочному выводу, что контрольное число, вычисленное по алгоритму Луна, подтверждает неизменность данных.
[править] Алгоритм проверки контрольной цифры
[править] Упрощённый алгоритм
1. Начиная с первой цифры слева через 1 (то есть 1, 3, 5, 7, 9, …) делается проверка: если 2·x > 9, то из произведения вычитается 9, если 2·x < 9, то произведение оставляем без изменения.
например:
4 5 6 1 2 6 1 2 1 2 3 4 5 4 6 7 8 12 4 2 2 6 10 12 8 3 4 2 2 6 1 3
2. Затем все числа складываются.
8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+7 = 60
3. Полученная сумма должна быть кратна 10 (40,50,60,70…)
В примере: последнее число — это контрольная цифра. Для того, чтобы номер был верен в соответствии с алгоритмом Луна, контрольная цифра должна быть равна 7.
4 5 6 1 2 6 1 2 1 2 3 4 5 4 6 7 8 12 4 2 2 6 10 12 8 3 4 2 2 6 1 3
8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+7 = 60
[править] Оригинальный алгоритм, описанный разработчиком
1. Цифры проверяемой последовательности нумеруются справа налево.
2. Цифры, оказавшиеся на нечётных местах, остаются без изменений.
3. Цифры, стоящие на чётных местах, умножаются на 2.
4. Если в результате такого умножения возникает число больше 9, оно заменяется суммой цифр получившегося произведения — однозначным числом, то есть цифрой.
5. Все полученные в результате преобразования цифры складываются. Если сумма кратна 10, то исходные данные верны.
[править] Модификации
Для шестнадцатеричной последовательности алгоритм видоизменяется следующим образом:
- Цифры нумеруются справа налево
- Каждая цифра, стоящая на нечетном месте, умножается на 2
- Если полученное число больше F16, то из произведения вычитается F16.
- Цифры, стоящие на четных местах складываются в результатами предыдущего шага.
- Если полученная сумма кратна 1016 (то есть 1610), то контрольная цифра указана верно.
Пример (в примере все числа — шестнадцатеричные):
A F 0 1 2 3 4 5 0 A B C D E С A 0 2 4 0 B D C 1E 2 6 A 14 18 1C F 2 6 A 5 9 D A+F+0+2+2+6+4+A+0+5+B+9+D+D+C=70 Контрольная цифра C указана верно.
[править] Аналоги
[править] Источники информации
- U.S. Patent 2 950 048 Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.
