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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм вычисления в переводе на язык 1С 7.7, 8.x

ШтрКод - исходные данные без последнего символа, Функция возвращает контрольный символ, который необходимо добавить


 Функция АлгоритмЛуна(ШтрКод) Экспорт
   N = СтрДлина(ШтрКод)+1;    
   sum = 0;
   Для i = 1 по N-1 Цикл
     p = Сред(ШтрКод,N-i,1);
     Если(i/2 <> Цел(i/2) ) Тогда
       p = 2*p;
       Если (p > 9) Тогда 
         p = p - 9;
       КонецЕсли;
     КонецЕсли;
     sum = sum + p;   
   КонецЦикла;
   sum = (sum/10) - Цел(sum/10);
   Если (sum <> 0) Тогда 
     sum = 10 - sum*10;
   КонецЕсли;      
   Сообщить("Контр.число ="+sum); 
   Возврат sum; 
 КонецФункции 

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

Pseudo-Code[править | править вики-текст]

 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;
  }

C#[править | править вики-текст]

   public static bool checkLuhn(string data)
   {
      int sum = 0;
      int len = data.Length;
      for (int i = 0; i < len; i++)
      {
         int add = (data[i] - '0') * (2 - (i + len) % 2);
         add -= add > 9 ? 9 : 0;
         sum += add;
      }
      return sum % 10 == 0;
   }

Go[править | править вики-текст]

func checkLuhn(purportedCC string) bool {
	var sum = 0
	var nDigits = len(purportedCC)
	var parity = nDigits % 2

	for i := 0; i < nDigits; i++ {
		var digit = int(purportedCC[i] - 48)
		if i%2 == parity {
			digit *= 2
			if digit > 9 {
			    digit -= 9
		    }
		}
		sum += digit
	}
	return sum%10 == 0
}

PHP[править | править вики-текст]

 function checkLuhn($number) {
     $sum = 0;
     $numDigits = strlen($number)-1;
     $parity = $numDigits % 2;
     for ($i = $numDigits; $i >= 0; $i--) {
         $digit = substr($number, $i, 1);
         if (!$parity == ($i % 2)) {$digit <<= 1;}
         $digit = ($digit > 9) ? ($digit - 9) : $digit;
         $sum += $digit;
     }
     return (0 == ($sum % 10));
 }

Java[править | править вики-текст]

   public static boolean check(int[] digits) {
       int sum = 0;
       int length = digits.length;
       for (int i = 0; i < length; i++) {

           // get digits in reverse order
           int digit = digits[length - i - 1];

           // every 2nd number multiply with 2
           if (i % 2 == 1) {
               digit *= 2;
           }
           sum += digit > 9 ? digit - 9 : digit;
       }
       return sum % 10 == 0;
   }

Python[править | править вики-текст]

    def checkLuhn(purportedCC=''):
        sum = 0
        parity = len(purportedCC) % 2
        for i, digit in enumerate([int(x) for x in purportedCC]):
            if i % 2 == parity:
                digit *= 2
                if digit > 9:
                    digit -= 9
            sum += digit
        return sum % 10 == 0

Haskell[править | править вики-текст]

checkluhnIntegral:: Integral a => a -> Bool
checkluhnIntegral i = (lunvalIntegral i) == 0

genluhnIntegral:: Integral a => a -> a
genluhnIntegral i = (10*i) + mod (10 - lunvalIntegral (10*i)) 10

lunvalIntegral:: Integral a => a -> a
lunvalIntegral i = mod (singleNext i) 10
                   where
                     singleNext 0 = 0
                     singleNext i = (mod i 10) + doubleNext (div i 10)
                     doubleNext 0 = 0
                     doubleNext i = (luhndouble (mod i 10)) + singleNext (div i 10)

luhndouble a = dsum (2*a)
dsum a | a < 10    = a
       | otherwise = (dsum (div a 10)) + (mod a 10)

ILE-RPG (IBM native)[править | править вики-текст]

D ccInvalidChar   C                   CONST('abcdefghi…')
…
 	§nLength = %len( %trim( §cString));

        for §nI = §nLength downto 1;
          §nJ = §nJ + 1;
          §cString1 = %subst( %trim( §cString): §nI : 1);
          MONITOR;
            §nInt = %DEC( %XLATE(ccInvalidChar: '0': §cString1): 1: 0);
          ON-ERROR 105;
            §nInt = 0;
          ENDMON;

          if %rem( §nJ: 2) = 0;
             §nInt = §nInt * 2;
          endif;

          if §nInt > 9;
            §cDigit1 = %subst( %char( §nInt): 1: 1);
            MONITOR;
              §nDigit1 = %dec( §cDigit1: 1: 0);
            ON-ERROR 105;
              §nDigit1 = 0;
            ENDMON;
            §cDigit2 = %subst( %char( §nInt): 2: 1);
            MONITOR;
              §nDigit2 = %dec( §cDigit2: 1: 0);
            ON-ERROR 105;
              §nDigit2 = 0;
            ENDMON;
            §nInt = §nDigit1 + §nDigit2;
          endif;
          §nResult = §nResult + §nInt;
        endfor;

        §nChkDigit = %rem( §nResult: 10);

Аналоги[править | править вики-текст]

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

Ссылки[править | править вики-текст]