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

Алгоритм Лу́на (англ. Luhn algorithm), также известный как алгоритм «модуля 10» или «mod 10» — алгоритм вычисления контрольной цифры номера пластиковой карты в соответствии со стандартом ISO/IEC 7812^[1]. Назван в честь его создателя, ученого из IBM Ханса Питера Луна^[англ.]. Алгоритм описан в 1954 году, патент получен в 1960 году^[2].

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

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

Номер локомотива на Deutsche Bahn с контрольной цифрой (2) в соответствии с алгоритмом Луна

Наиболее распространённые применения

• Номера банковских карт^[англ.]
• Номера некоторых дисконтных карт
• Коды социального страхования
• IMEI-коды
• ICCID (англ. integrated circuit card identifier) — уникальный серийный номер SIM-карты
• Единый 8-значный номер железнодорожного вагона на РЖД

Достоинства и недостатки

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

Алгоритм может применяться для последовательностей цифр любой длины, однако при этом следует иметь в виду, что при достаточно длинных числах вероятно появление одновременно нескольких искажений данных. Некоторые из таких ошибок могут привести к ошибочному выводу, что контрольное число, вычисленное по алгоритму Луна, подтверждает неизменность данных.

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

Оригинальный алгоритм

1. Начиная с первой цифры последовательности слева и через одну цифру (то есть позиции 1, 3, 5, 7, 9, …) в случае, если количество цифр в последовательности нечетное (как в этом примере, где оно равно 15, 16-я — контрольная), если же количество цифр четное, тогда, начиная со второй цифры последовательности через одну цифру (то есть позиции 2, 4, 6, 8, …), делается проверка: если 2·x > 9, то из произведения вычитается 9, иначе произведение 2·x оставляем без изменения, где x — текущая цифра.

Например:

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

Алгоритм на псевдокоде

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

function checkLuhn(ccn) {
  const ccnS = ccn.toString();
  let sum = 0;
  const parity = (ccnS.length) % 2;
  for (let i = 0; i < ccnS.length; i += 1) {
    let digit = Number(ccnS[i]);
    if (i % 2 === parity) {
      digit *= 2;
      if (digit > 9) {
        digit -= 9;
      }
    }
    sum += digit;
  }
  return Number(sum % 10) === 0;
}

Литература

• U.S. Patent 2 950 048 Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.