Алгоритм Луна (англ. Luhn algorithm), або формула Луна (англ. Luhn formula), також відомий під назвою «modulus 10» або «mod 10», це проста формула перевірки контрольної суми, що використовується для валідації різноманітних ідентифікаційних номерів, таких як номери кредитних/платіжних карток, номери IMEI, американських , канадських , ізраїльських ID Numbers та грецьких Social Security Numbers (ΑΜΚΑ). Алгоритм був створений науковцем з IBM [en] і описаний патентом U.S. Patent No. 2,950,048, описаним 6 січня 1954 року та схваленим 23 серпня 1960 року.
Алгоритм є публічним і широко використовується. Він також вказаний у [en]. Цей алгоритм не створювався як криптографічно надійна хеш-функція, а суто як захист від випадкових помилок. Більшість кредитних карток і багато урядових ідентифікаційних номерів використовують цей алгоритм як простий метод відсіювання неправильних номерів.
Опис
Формула перевіряє номер за його контрольною цифрою, котра зазвичай додається до часткового номера акаунту (partial account number) при генеруванні повного номера акаунту (full account number). Цей номер повинен успішно проходити таку перевірку:
- Починаючи від крайньої правої цифри (контрольної), рухаємося ліворуч, подвоюючи кожну другу цифру. Якщо результат подвоєння є більшим, ніж 9 (як-от: 8 × 2 = 16), то потрібно додати числа результату (наприклад: 16: 1 + 6 = 7, 18: 1 + 8 = 9), або, як альтернатива — відняти 9 від результату (16: 16 − 9 = 7, 18: 18 − 9 = 9).
- Знайти суму всіх цифр.
- Якщо ділення суми на 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). У формі алгоритму:
- Обчислити суму цифр без контрольної (67).
- Помножити на 9 (603).
- Остання цифра (3) буде контрольною цифрою, як-от x=3.
Альтернативний метод: контрольна цифра (x) отримується в результаті суми решти цифр (3 рядок), ділення її на 10 з остачею, і віднімання цієї остачі від 10 (остача (67/10) = 7; 10 − 7 = 3). В алгоритмічній формі:
- Вирахувати суму цифр без контрольної (67).
- Отримати остачу (7).
- Відняти остачу від 10.
- Результат (3) є контрольною цифрою. Якщо сума закінчується нулем, то нуль буде контрольною цифрою.
Відповідно повний номер акаунту матиме вигляд 79927398713.
Кожен з номерів 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 може пройти перевірку наступним чином:
- Подвоїти цифри через одну, починаючи з крайньої правої: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
- Додати всі окремі цифри (цифри в дужках є результатами кроку 1): x (контрольна цифра) + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 7 = x + 67.
- Якщо сума ділиться без остачі на 10, то номер може бути правильним. Зверніть увагу, що 3 — це єдина правильна контрольна цифра, котра поверне суму (70), яка ділиться на 10 без остачі.
- Отже всі ці номери є неправильними, окрім 79927398713, котрий має правильну контрольну цифру.
Ви можете також використати той самий алгоритм створення контрольної суми, припускаючи що наявна перевірка контрольної суми насправді відсутня. Тоді порахуйте контрольну суму і порівняйте результат із оригінальною контрольною сумою, наявною в кредитної картки. Якщо оригінальна контрольна сума відповідає порахованій, то номер є правильним.
Переваги та недоліки
Алгоритм Луна може знайти помилку в одній цифрі, так само як і всі перестановки сусідніх цифр, проте він не може виявити перестановку двоцифрових послідовностей 09 - 90 (чи навпаки). Він виявлятиме також 7 із 10 можливих помилок дублювання (але не виявить 22 ↔ 55, 33 ↔ 66 або 44 ↔ 77).
Інші, складніші алгоритми перевірки контрольної цифри (такі як алгоритм Вергуффа чи алгоритм Дамма) можуть знаходити більше помилок. Існує ще алгоритм Луна 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 }
Посилання
Ця стаття не містить . (листопад 2017) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Luna angl Luhn algorithm abo formula Luna angl Luhn formula takozh vidomij pid nazvoyu modulus 10 abo mod 10 ce prosta formula perevirki kontrolnoyi sumi sho vikoristovuyetsya dlya validaciyi riznomanitnih identifikacijnih nomeriv takih yak nomeri kreditnih platizhnih kartok nomeri IMEI amerikanskih kanadskih izrayilskih ID Numbers ta greckih Social Security Numbers AMKA Algoritm buv stvorenij naukovcem z IBM en i opisanij patentom U S Patent No 2 950 048 opisanim 6 sichnya 1954 roku ta shvalenim 23 serpnya 1960 roku Algoritm ye publichnim i shiroko vikoristovuyetsya Vin takozh vkazanij u en Cej algoritm ne stvoryuvavsya yak kriptografichno nadijna hesh funkciya a suto yak zahist vid vipadkovih pomilok Bilshist kreditnih kartok i bagato uryadovih identifikacijnih nomeriv vikoristovuyut cej algoritm yak prostij metod vidsiyuvannya nepravilnih nomeriv OpisFormula pereviryaye nomer za jogo kontrolnoyu cifroyu kotra zazvichaj dodayetsya do chastkovogo nomera akauntu partial account number pri generuvanni povnogo nomera akauntu full account number Cej nomer povinen uspishno prohoditi taku perevirku Pochinayuchi vid krajnoyi pravoyi cifri kontrolnoyi ruhayemosya livoruch podvoyuyuchi kozhnu drugu cifru Yaksho rezultat podvoyennya ye bilshim nizh 9 yak ot 8 2 16 to potribno dodati chisla rezultatu napriklad 16 1 6 7 18 1 8 9 abo yak alternativa vidnyati 9 vid rezultatu 16 16 9 7 18 18 9 9 Znajti sumu vsih cifr Yaksho dilennya sumi na 10 ne maye ostachi suma zakinchuyetsya nulem to nomer ye pravilnim vidpovidno do formuli Luna Nehaj u nas ye nomer 7992739871 yakij matime kontrolnu cifru v nastupnomu viglyadi 7992739871x Todi Nomer 7 9 9 2 7 3 9 8 7 1 x Podvoyiti cherez odnu 7 18 9 4 7 6 9 16 7 2 x Dodati cifri 7 9 9 4 7 6 9 7 7 2 x Suma vsih cifr u tretomu ryadku dorivnyuvatime 67 x Kontrolnu cifru x mozhna otrimati mnozhennyam sumi cifr na 9 i dilennyam rezultatu na 10 67 9 mod 10 U formi algoritmu Obchisliti sumu cifr bez kontrolnoyi 67 Pomnozhiti na 9 603 Ostannya cifra 3 bude kontrolnoyu cifroyu yak ot x 3 Alternativnij metod kontrolna cifra x otrimuyetsya v rezultati sumi reshti cifr 3 ryadok dilennya yiyi na 10 z ostacheyu i vidnimannya ciyeyi ostachi vid 10 ostacha 67 10 7 10 7 3 V algoritmichnij formi Virahuvati sumu cifr bez kontrolnoyi 67 Otrimati ostachu 7 Vidnyati ostachu vid 10 Rezultat 3 ye kontrolnoyu cifroyu Yaksho suma zakinchuyetsya nulem to nul bude kontrolnoyu cifroyu Vidpovidno povnij nomer akauntu matime viglyad 79927398713 Kozhen z nomeriv 79927398710 79927398711 79927398712 79927398713 79927398714 79927398715 79927398716 79927398717 79927398718 79927398719 mozhe projti perevirku nastupnim chinom Podvoyiti cifri cherez odnu pochinayuchi z krajnoyi pravoyi 1 2 2 8 2 16 3 2 6 2 2 4 9 2 18 Dodati vsi okremi cifri cifri v duzhkah ye rezultatami kroku 1 x kontrolna cifra 2 7 1 6 9 6 7 4 9 1 8 7 x 67 Yaksho suma dilitsya bez ostachi na 10 to nomer mozhe buti pravilnim Zvernit uvagu sho 3 ce yedina pravilna kontrolna cifra kotra poverne sumu 70 yaka dilitsya na 10 bez ostachi Otzhe vsi ci nomeri ye nepravilnimi okrim 79927398713 kotrij maye pravilnu kontrolnu cifru Vi mozhete takozh vikoristati toj samij algoritm stvorennya kontrolnoyi sumi pripuskayuchi sho nayavna perevirka kontrolnoyi sumi naspravdi vidsutnya Todi porahujte kontrolnu sumu i porivnyajte rezultat iz originalnoyu kontrolnoyu sumoyu nayavnoyu v kreditnoyi kartki Yaksho originalna kontrolna suma vidpovidaye porahovanij to nomer ye pravilnim Perevagi ta nedolikiAlgoritm Luna mozhe znajti pomilku v odnij cifri tak samo yak i vsi perestanovki susidnih cifr prote vin ne mozhe viyaviti perestanovku dvocifrovih poslidovnostej 09 90 chi navpaki Vin viyavlyatime takozh 7 iz 10 mozhlivih pomilok dublyuvannya ale ne viyavit 22 55 33 66 abo 44 77 Inshi skladnishi algoritmi perevirki kontrolnoyi cifri taki yak algoritm Verguffa chi algoritm Damma mozhut znahoditi bilshe pomilok Isnuye she algoritm Luna mod N Luhn mod N algorithm yakij ye rozshirennyam zvichajnogo i dodaye pidtrimku necifrovih ryadkiv Oskilki algoritm operuye ciframi sprava nalivo i nuli vplivayut na rezultat tilki todi koli voni viklikayut zmishennya poziciyi to nuli na pochatku poslidovnosti cifr ne vplinut na rozrahunok Vnaslidok cogo sistemi yaki mayut na pochatku pevnu kilkist cifr napriklad pri konvertuvanni 1234 v 0001234 mozhut prohoditi perevirku algoritmom Luna z nulyami abo bez nih i vidavati odnakovi rezultati Dodavannya 0 do nomeriv neparnoyi dovzhini dozvolyaye pereviryati nomeri zliva napravo a ne navpaki z podvoyennyam cifr na neparnih miscyah Algoritm z yavivsya v amerikanskomu patenti dlya ruchnogo mehanichnogo pristroyu dlya obrahunku kontrolnih sum a tomu osnovnoyu vimogoyu do algoritmu bula vidnosna prostota realizaciyi Mehanizm pristroyu diliv sumu na 10 ale cifri vid podvoyennya ta nastupnoyi redukciyi ne otrimuvalisya mehanichnim shlyahom a poznachalisya u zminenomu poryadku na samomu pristroyi Prikladi implementaciyiPsevdokod 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 gt 9 digit digit 9 sum sum digit return sum modulus 10 0 PosilannyaCya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno listopad 2017