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

Алгоритм Лу́на (англ. Luhn algorithm), алгоритм вычисления контрольной цифры номера пластиковых карт в соответствии со стандартом ISO/IEC 7812. Не является криптографическим средством, предназначение алгоритма в первую очередь — выявление ошибок, вызванных непреднамеренным искажением данных (например, при ручном вводе номера карты, при приёме данных о номере социального страхования по телефону). Позволяет лишь с некоторой степенью достоверности судить об отсутствии ошибок в блоке цифр, но не даёт возможности локализации и коррекции обнаруженной неточности.

Алгоритм разработан сотрудником фирмы IBM Гансом Питером Луном, описан в США в 1954 году, патент получен в 1960 году.

Наиболее распространённые применения для подсчёта контрольной цифры:

• Номера всех банковских карт

• Номера некоторых дисконтных карт

• Коды социального страхования

• IMEI-коды.

В настоящее время содержание алгоритма является публичным достоянием.

В силу простоты реализации, алгоритм отнимает минимум вычислительных мощностей; в ряде случаев при наличии навыка расчёт может быть произведён в уме. В то же время, А.Л. позволяет только выявить ошибки в блоках данных, и то не все. Искажение одной цифры — обнаруживается. Обнаруживаются практически все парные перестановки подряд идущих цифр (за исключением 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 4

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+4 = 57

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, то исходные данные верны.

[править]Алгоритм вычисления контрольной цифры

Num[1..N] — номер карты, Num[N] — контрольная цифра

sum = 0

for i = 1 to N-1 do

p = Num[N-i]

if (i mod 2 == 0) then

p = 2*p

if (p > 9) then

p = p - 9

end if

end if

sum = sum + p

next i

//дополнение до 10

sum = (10 - (sum mod 10) mod 10)

Num[N] = sum