Замечания к алгоритму Луна (Luhn algorithm)

Июль 11, 2012 — Шарахов А.П.

Давайте посмотрим, насколько сильно отличаются алгоритмы Луна и Верхоффа.

Зри в корень

Если разобраться, модифицированное умножение на 2 в алгоритме Луна — это обычная замена цифр с использованием перестановки

0, 2, 4, 6, 8, 1, 3, 5, 7, 9

Оказывается, что при выборе этой перестановки суммы нескольких пар повторяются, например: 22=55, 33=66, 44=77. В то же время существует 2800 перестановок с периодами от 4 до 20, которые гораздо менее 'похожи' на тождественную перестановку (в смысле меньшей повторяемости пар). Возьмем, например, перестановку номер 381522:

1, 0, 5, 7, 9, 3, 8, 2, 4, 6

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

Варить до готовности

Очевидно, что алгоритм Луна совсем не замечает перестановок цифр в позициях одинаковой четности на расстоянии 2. Также очевидно, что для каждой из упомянутых выше 2800 перестановок существует 2800 'непохожих' на нее перестановок, среди которых, в частности, есть она сама. Т.к. период выбранной нами перестановки равен 4, то мы можем разделить позиции не на 2 группы (чет/нечет) как в оригинальном алгоритме, а на 4 группы в зависимости от остатка от деления номера позиции на 4.
В каждых четырех последовательных позициях будем использовать нашу перестановку в соответствующей степени. Благодаря этому алгоритм начинает замечать большое количество ошибок в ближайших позициях одинаковой четности. После всех усовершенствований он приобретает вид: 

//Sha 2012
//ver 2012-07-11
//Free for any use
 
(*--------------------------------------------------------------------------------------------------
Luhn algorithm:
Counting from the check digit, which is the rightmost, and moving left, double the value
of every second digit. Sum the digits of the products (e.g., 14 = 1 + 4 = 5) together
with the undoubled digits. If the total modulo 10 is equal to 0 then the number is valid.
----------------------------------------------------------------------------------------------------
Modified version detects more "aa=bb", "acb=bca", "1a=a0", skips more "aca=bcb" errors
and produces non-standart check digit.
--------------------------------------------------------------------------------------------------*)
 
unit Luhn;
 
interface
 
function LuhnCalculateChar(const s: string): char;
function LuhnValidateString(const s: string): boolean;
function LuhnSelfTest: boolean;
procedure LuhnInit(SubNo: integer= 0);
 
implementation
 
var
  //The permutation table
  p: array[0..3,0..9] of byte = (
    (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),   // * 1
    (0, 2, 4, 6, 8, 1, 3, 5, 7, 9),   // * 2
    (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),   // * 1
    (0, 2, 4, 6, 8, 1, 3, 5, 7, 9));  // * 2
 
function LuhnCalculateChar(const s: string): char;
var
  len, c, i, j: integer;
begin;
  len:=Length(s);
  c:=0;
  i:=1; //count from 1 not 0! because where is no check digit in the string
  while len>0 do begin;
    j:=ord(s[len])-ord('0');
    if (j<0) or (j>9) then break;
    c:=c + p[i and 3, j];
    dec(len);
    inc(i);
    end;
  c:=c mod 10;
  if c>0 then c:=10-c;
  Result:=chr(c+ord('0'));
  end;
 
function LuhnValidateString(const s: string): boolean;
var
  len, c, i, j: integer;
begin;
  len:=Length(s);
  c:=0;
  i:=0; //count from 0, because where is check digit in the string
  while len>0 do begin;
    j:=ord(s[len])-ord('0');
    if (j<0) or (j>9) then break;
    c:=c + p[i and 3, j];
    dec(len);
    inc(i);
    end;
  Result:=(c mod 10 or len=0);
  end;
 
function LuhnSelfTest: boolean;
begin;
  Result:=(LuhnCalculateChar('7992739871')='3')
      and LuhnValidateString('79927398713')
      and not LuhnValidateString('79927398712');
  end;
 
var
  Sub: array[0..1,0..9] of byte= (
    (0, 2, 4, 6, 8, 1, 3, 5, 7, 9),  // standard permutation
    (1, 0, 5, 7, 9, 3, 8, 2, 4, 6)); // permutation #381522
 
procedure LuhnInit(SubNo: integer= 0);
var
  i, j: integer;
begin;
  SubNo:=SubNo and 1;
  for j:=0 to 9 do p[0,j]:=j;
  for j:=0 to 9 do p[1,j]:=Sub[SubNo,j];
  if SubNo=0 then begin;
    for j:=0 to 9 do p[2,j]:=j;
    for j:=0 to 9 do p[3,j]:=Sub[SubNo,j];
    end
  else for i:=2 to 3 do for j:=0 to 9 do p[i,j]:=p[i-1,p[1,j]];
  end;
 
initialization
 
  //LuhnInit(0);
 
end.

Еще десять тысяч ведер

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

на главную