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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Алгоритм Луна (англ. Luhn algorithm), або формула Луна (англ. Luhn formula), також відомий під назвою «modulus 10» або «mod 10», це проста формула перевірки контрольної суми, що використовується для валідації різноманітних ідентифікаційних номерів, таких як номери кредитних/платіжних карток, номери IMEI, американських National Provider Identifier Number, канадських Canadian Social Insurance Number, ізраїльських ID Numbers та грецьких Social Security Numbers (ΑΜΚΑ). Алгоритм був створений науковцем з IBM Гансом Петером Луном[en] і описаний патентом U.S. Patent No. 2,950,048, описаним 6 січня 1954 року та схваленим 23 серпня 1960 року.

Алгоритм є публічним і широко використовується. Він також вказаний у ISO/IEC 7812[en]. Цей алгоритм не створювався як криптографічно надійна хеш-функція, а суто як захист від випадкових помилок. Більшість кредитних карток і багато урядових ідентифікаційних номерів використовують цей алгоритм як простий метод відсіювання неправильних номерів.

Опис[ред. | ред. код]

Формула перевіряє номер за його контрольною цифрою, котра зазвичай додається до часткового номера акаунту (partial account number) при генеруванні повного номера акаунту (full account number). Цей номер повинен успішно проходити таку перевірку:

  1. Починаючи від крайньої правої цифри (контрольної), рухаємося ліворуч, подвоюючи кожну другу цифру. Якщо результат подвоєння є більшим, ніж 9 (як-от: 8 × 2 = 16), то потрібно додати числа результату (наприклад: 16: 1 + 6 = 7, 18: 1 + 8 = 9), або, як альтернатива — відняти 9 від результату (16: 16 − 9 = 7, 18: 18 − 9 = 9).
  2. Знайти суму всіх цифр.
  3. Якщо ділення суми на 10 не має остачі (сума закінчується нулем,) то номер є правильним відповідно до формули Луна.

Нехай у нас є номер «7992739871», який матиме контрольну цифру в наступному вигляді: 7992739871x. Тоді:

Номер 7 9 9 2 7 3 9 8 7 1 x
Подвоїти через одну 7 18 9 4 7 6 9 16 7 2 x
Додати цифри 7 9 9 4 7 6 9 7 7 2 x

Сума всіх цифр у третьому рядку дорівнюватиме 67+x.

контрольна цифра (x) отримана множенням суми цифр на 9 і діленням результату на 10 ((67 × 9) mod 10). У формі алгоритму:

  1. Обчислити суму цифр без контрольної (67).
  2. Помножити на 9 (603).
  3. Цифра остачі (3) буде контрольною цифрою, як-от x=3.

(Альтернативний метод) контрольна цифра (x) отримується розрахунком суми решти цифр (3 рядок), діленням її на 10 з остачею, і відніманням цієї остачі від 10. (67 => остача 7; 10 − 7 = контрольна цифра 3) Або у алгоритмічній формі:

  1. Вирахувати суму цифр без контрольної (67).
  2. Отримати остачу (7).
  3. Відняти остачу від 10.
  4. Результат (3) є контрольною цифрою. Якщо сума закінчується нулем, то нуль буде контрольною цифрою.

Відповідно повний номер акаунту матиме вигляд 79927398713.

Кожен з номерів 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 може пройти перевірку наступним чином:

  1. Подвоїти цифри через одну, починаючи з крайньої правої: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
  2. Додати всі окремі цифри (цифри в дужках є результатами кроку 1): x (контрольна цифра) + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 7 = x + 67.
  3. Якщо сума ділиться без остачі на 10, то номер може бути правильним. Зверніть увагу, що 3 — це єдина правильна контрольна цифра, котра поверне суму (70), яка ділиться на 10 без остачі.
  4. Отже всі ці номери є неправильними, окрім 79927398713, котрий має правильну контрольну цифру.

Також, ви можете використати той самий алгоритм створення контрольної суми, припускаючи що наявна перевірка контрольної суми насправді відсутня. Тоді порахуйте контрольну суму і порівняйте результат із оригінальною контрольною сумою, наявною в кредитної картки. Якщо оригінальна контрольна сума відповідає порахованій, то номер є правильним.

Переваги та недоліки[ред. | ред. код]

Алгоритм Луна може знайти помилку в одній цифрі, так само як і всі перестановки сусідніх цифр, проте він не може виявити перестановку двоцифрових послідовностей 09 to 90 (чи навпаки). Також він виявлятиме 7 із 10 можливих помилок дублювання (але не виявить 2255, 3366 або 4477).

Інші, складніші алгоритми перевірки контрольної цифри (такі як алгоритм Вергуффа чи алгоритм Дамма) можуть знаходити більше помилок. Існує ще алгоритм Луна mod N (Luhn mod N algorithm), який є розширенням звичайного і додає підтримку нецифрових рядків.

Оскільки алгоритм оперує цифрами справа наліво і нулі впливають на результат тільки тоді, коли вони викликають зміщення позиції, то нулі на початку послідовності цифр не вплинуть на розрахунок. Внаслідок цього, системи, які мають на початку певну кількість цифр (наприклад при конвертуванні 1234 в 0001234,) можуть проходити перевірку алгоритмом Луна з нулями або без них і видавати однакові результати.

Додавання 0 до номерів непарної довжини дозволяє перевіряти номери зліва направо, а не навпаки, з подвоєнням цифр на непарних місцях.

Алгоритм з'явився у американському патенті для ручного механічного пристрою для обрахунку контрольних сум, а тому основною вимогою до алгоритму була порівняна простота реалізації. Механізм пристрою ділив суму на 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
 }

Посилання[ред. | ред. код]