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

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

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

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

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

  • Номера всех банковских карт
  • Номера некоторых дисконтных карт
  • Коды социального страхования
  • IMEI-коды.

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

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

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


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

var
 sum: real;
 i,p,N: integer;
 Num: Array [1..N] of integer;

begin
 sum := 0;
 for i := 0 to N-1 do
 begin
   p := Num[N-i];    
   if i mod 2 <> 0 then p := 2*p;
   if p > 9 then p := p - 9;
   sum := sum + p;
 end;
 //дополнение до 10 
 sum := 10 - (sum mod 10);
 if sum = 10 then sum := 0;
 Num[N] := sum;
end;

   Массив = Новый Массив();
        Для i = 0 по ДлинаНомера() - 1 Цикл
                Массив.Добавить(Число(Сред(Текст,i+1,1)));
        КонецЦикла;
        Сумма = 0;
        Для i = 0 по ДлинаНомера() - 1 Цикл
                Сумма = Сумма + (?(Массив[i]*2>9,Массив[i]*2-9,Массив[i]*2) + Массив[i+1]);
                Если i < Массив.ВГраница()-1 Тогда 
                        i = i+1;
                Иначе
                        Прервать;
                КонецЕсли;
        КонецЦикла;
        
        Если Цел(Сумма/10) <> Сумма/10 Тогда
                Предупреждение("Номер карты заполнен не верно!")                
        КонецЕсли;      

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

Алгоритм Верхоффа

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

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