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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Достоинства и недостатки[править | править код]

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

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

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

Упрощённый алгоритм[править | править код]

1. Начиная с первой цифры последовательности слева и через одну цифру (то есть позиции 1, 3, 5, 7, 9, …) в случае, если количество цифр в последовательности четное (как в этом примере, где оно равно 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, то исходные данные верны.

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

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)
 if (sum == 10) then 
   sum = 0
 end if
 Num[N] = sum

Примеры реализации[править | править код]

Псевдокод[править | править код]

 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
 }

C[править | править код]

  #include <stdlib.h> // atoi
  #include <string.h> // strlen
  #include <stdbool.h> // bool

  bool checkLuhn(const char *pPurported)
  {
    int nSum       = 0;
    int nDigits    = strlen(pPurported);
    int nParity    = (nDigits-1) % 2;
    char cDigit[2] = "\0";
    for (int i = nDigits; i > 0 ; i--)
    {
      cDigit[0]  = pPurported[i-1];
      int nDigit = atoi(cDigit);

      if (nParity == i % 2)
        nDigit = nDigit * 2;

      nSum += nDigit/10;
      nSum += nDigit%10;
    }
    return 0 == nSum % 10;
  }

Python[править | править код]

from functools import reduce

def luhn(code):
    # Предварительно рассчитанные результаты умножения на 2 с вычетом 9 для больших цифр
    # Номер индекса равен числу над которым проводится операция
    LOOKUP = (0, 2, 4, 6, 8, 1, 3, 5, 7, 9)
    code = reduce(str.__add__, filter(str.isdigit, code))
    evens = sum(int(i) for i in code[-1::-2])
    odds = sum(LOOKUP[int(i)] for i in code[-2::-2])
    return ((evens + odds) % 10 == 0)

print("Прошел проверку: ", luhn('4561 2612 1234 5467'))
print("Не прошел проверку: ", luhn('4561 2612 1234 5464'))

JavaScript[править | править код]

function luhnAlgorithm(digits) {
  let sum = 0;

  for (let i = 0; i < digits.length; i++) {
    let cardNum = parseInt(digits[i]);

    if ((digits.length - i) % 2 === 0) {
      cardNum = cardNum * 2;

      if (cardNum > 9) {
        cardNum = cardNum - 9;
      }
    }

    sum += cardNum;
  }

  return sum % 10 === 0;
}

PHP

function luhnAlgorithm($digit)
{
    $number = strrev(preg_replace('/[^\d]/', '', $digit));
    $sum = 0;
    for ($i = 0, $j = strlen($number); $i < $j; $i++) {
        if (($i % 2) == 0) {
            $val = $number[$i];
        } else {
            $val = $number[$i] * 2;
            if ($val > 9)  {
                $val -= 9;
            }
        }
        $sum += $val;
    }
    return (($sum % 10) === 0);
}

Kotlin

fun luhnAlgorithm(cardNumber: String): Boolean {
    val digits = cardNumber.map { Character.getNumericValue(it) }.toMutableList()
    for (i in (digits.size - 2) downTo 0 step 2) {
        var value = digits[i] * 2
        if (value > 9) {
            value = value % 10 + 1
        }
        digits[i] = value
    }
    return digits.sum() % 10 == 0
}

Источники информации[править | править код]

Ссылки[править | править код]