Алгарытм Лу́на (англ.: Luhn algorithm), або формула Луна, або алгарытм Мод10 — алгарытм вылічэння кантрольнага ліку нумара пластыкавых картак у адпаведнасці са стандартам ISO/IEC 7812. Не з'яўляецца крыптаграфічным сродкам, прызначэнне алгарытму ў першую чаргу - выяўленне памылак, выкліканых ненаўмысным скажэннем даных (напрыклад, пры ручным уводзе нумара карткі, пры прыёме даных аб нумары сацыяльнага страхавання праз тэлефон). Дазваляе толькі з некаторай ступенню пэўнасці судзіць аб адсутнасці памылак у блоку лікаў, але не дае магчымасці лакалізацыі і карэкцыі выяўленай недакладнасці.
Алгарытм распрацаваны супрацоўнікам фірмы IBM Гансам Пітэрам Лунам, апісаны ў ЗША ў 1954 годзе, патэнт атрыманы ў 1960 годзе.
Найбольш распаўсюджаныя ўжыванні для падліку кантрольнга ліку:
У цяперашні час змест алгарытму з'яўляецца грамадскім здабыткам.
У сілу прастаты рэалізацыі, алгарытм спажывае мінімум вылічальных магутнасцяў; у шэрагу выпадкаў пры наяўнасці навыка разлік можа быць выкананы ў уме. У той жа час, алгарытм Луна дазваляе толькі выявіць памылкі ў блоках даных, і нават не ўсе. Скажэнне адной лічбы выяўляецца. ВЫяўляюцца амаль усе парныя перастаноўкі лічбаў, якія ідуць запар (за выключэннем 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, то зыходны радок правільны.
На ўваходзе функцыі: масіў const int* card_number з 16 лічбаў (прадстаўлена ў выглядзе макросу #define CARD_LENGTH 16), кожная лічба не меней за 0 і не болей за 9. Гэты масіў - нумар карткі для верыфікацыі.
На выхадзе функцыі: значэнне тыпу int, 1, калі нумар карткі валідны, 0 - інакш.
У функцыі прадугледжана санітызацыя даных на ўваходзе. Калі масіў на ўваходзе не з'яўляецца нумарам карткі, то функцыя заканчваецца датэрмінова.
# include <assert.h>
# define ARRAY_LENGTH(x) (sizeof(x) / sizeof((x)[0]))
# define CARD_LENGTH 16
int luhn_verify(const int* card_number) {
int card_number_next_digit = 0;
int checksum = 0;
int i;
assert(card_number)
assert(ARRAY_LENGTH(card_number) == CARD_LENGTH);
for(i = 0; i < CARD_LENGTH; i++) {
assert(card_number[i] >= 0 && card_number[i] <= 9);
}
for(i = 0; i < CARD_LENGTH; i++) {
card_number_next_digit = card_number[i];
if(i % 2 != 0) {
card_number_next_digit *= 2;
if(card_number_next_digit > 9) {
card_number_next_digit -= 9;
}
}
checksum += card_number_next_digit;
}
return !(checksum % 10);
}
На ўваходзе функцыі: масіў card_number з 16 лічбаў (прадстаўлена ў выглядзе канстанты const CARDNUMBER_LENGTH = 16), кожная лічба не меней за 0 і не болей за 9. Гэты масіў - нумар карткі для верыфікацыі.
На выхадзе функцыі: значэнне тыпу Boolean, true, калі нумар карткі валідны, false - інакш.
У функцыі прадугледжана санітызацыя даных на ўваходзе. Калі масіў на ўваходзе не з'яўляецца нумарам карткі, то функцыя заканчваецца датэрмінова - кідае выключэнне.
const assert = require("assert")
const CARDNUMBER_LENGTH = 16
module.exports = (card_number) => {
assert(card_number)
assert.equal(card_number.length, CARDNUMBER_LENGTH)
let i
for (i = 0; i < CARDNUMBER_LENGTH; i++) {
assert(card_number[i] >= 0 && card_number[i] <= 9)
}
let checksum
for (i = 0; i < CARDNUMBER_LENGTH; i++) {
checksum += i % 2 ? (card_number[i] * 2 - (card_number[i] * 2 > 9 ? 0 : 9)) : card_number[i]
}
return Boolean(!(checksum % 10))
}
На ўваходзе функцыі: масіў int[] cardNumber з 16 лічбаў (прадстаўлена ў выглядзе канстантнага статычнага поля public static final int CARDNUMBER_LENGTH), кожная лічба не меней за 0 і не болей за 9. Гэты масіў - нумар карткі для верыфікацыі.
На выхадзе функцыі: значэнне тыпу boolean, true, калі нумар карткі валідны, false - інакш.
У функцыі прадугледжана санітызацыя даных на ўваходзе. Калі масіў на ўваходзе не з'яўляецца нумарам карткі, то функцыя выкідвае выключэнне і заканчваецца датэрмінова.
import java.util.*;
import java.lang.String;
public class LuhnVerifier {
public static final CARDNUMBER_LENGTH = 16;
public static boolean verify(int[] cardNumber) {
if (cardNumber.length() != CARDNUMBER_LENGTH) {
throw new Exception();
}
for (int i = 0; i < CARDNUMBER_LENGTH; i++) {
if (cardNumber[i] > 9 || cardNumber[i] < 0) {
throw new Exception();
}
}
int checksum = 0;
int cardNumberNextDigit;
for (int i = 0; i < CARDNUMBER_LENGTH; i++){
cardNumberNextDigit = cardNumber[i];
if (i % 2 != 0){
cardNumberNextDigit *= 2;
if (cardNumberNextDigit > 9) {
cardNumberNextDigit -= 9;
}
}
checksum += cardNumberNextDigit;
}
return checksum % 10 == 0;
}
}
function luhn_verify(card_number: array of Integer): Boolean;
var
i, card_number_next_digit, checksum: integer;
begin
checksum:= 0;
for i := High(card_number) downto Low(card_number) do
begin
card_number_next_digit := card_number[i];
if i mod 2 = 0 then
card_number_next_digit := 2 * card_number_next_digit;
if card_number_next_digit > 9 then
card_number_next_digit := card_number_next_digit - 9;
checksum := checksum + card_number_next_digit;
end;
Result := checksum mod 10 = 0;
end;