Алгарытм Лу́на (англ.: Luhn algorithm), або формула Луна, або алгарытм Мод10 — алгарытм вылічэння кантрольнага ліку нумара пластыкавых картак у адпаведнасці са стандартам ISO/IEC 7812. Не з’яўляецца крыптаграфічным сродкам, прызначэнне алгарытму ў першую чаргу - выяўленне памылак, выкліканых ненаўмысным скажэннем даных (напрыклад, пры ручным уводзе нумара карткі, пры прыёме даных аб нумары сацыяльнага страхавання праз тэлефон). Дазваляе толькі з некаторай ступенню пэўнасці судзіць аб адсутнасці памылак у блоку лікаў, але не дае магчымасці лакалізацыі і карэкцыі выяўленай недакладнасці.
Алгарытм распрацаваны супрацоўнікам фірмы IBM Гансам Пітэрам Лунам(англ.) бел., апісаны ў ЗША ў 1954 годзе, патэнт атрыманы ў 1960 годзе.
Найбольш распаўсюджаныя ўжыванні для падліку кантрольнга ліку:
У цяперашні час змест алгарытму з’яўляецца грамадскім здабыткам.
У сілу прастаты рэалізацыі, алгарытм спажывае мінімум вылічальных магутнасцяў; у шэрагу выпадкаў пры наяўнасці навыка разлік можа быць выкананы ў уме. У той жа час, алгарытм Луна дазваляе толькі выявіць памылкі ў блоках даных, і нават не ўсе. Скажэнне адной лічбы выяўляецца. ВЫяўляюцца амаль усе парныя перастаноўкі лічбаў, якія ідуць запар (за выключэннем 09 ↔ 90). Не могуць быць выяўлены некаторыя скажэнні двух літар запар, а дакладна 22 ↔ 55, 33 ↔ 66 і 44 ↔ 77. Алгарытм не дае інфармацыі аб месцы і характары ўзніклай памылкі.
Алгарытм можа ўжывацца для паслядоўнасцяў лічбаў любой даўжыні, аднак пры гэтым варта мець на ўвазе, што на досыць доўгіх паслядоўнасцях лікаў магчыма з’яўленне адначасова некалькіх скажэнняў даных; некаторыя з такіх памылак могуць прывесці да памылковай высновы, што кантрольны лік, вылічаны алгарытмам Луна, пацвярджае нязменнаць даных.
Напрыклад:
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
8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+4 = 57
У прыкладзе: апошні лік — гэта кантрольная лічба. Для таго, каб радок быў правільны ў адпаведнасці с алгарытмам Луна, кантрольная лічба павінна быць роўнай 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
Лічбы патрэбнай паслядоўнасці нумаруюцца справа налева.
Лічбы, якія апынуліся на няцотных месцах, застаюцца без зменаў.
Лічбы, якія знаходзяцца на цотных месцах, памнажаюцца на 2.
Калі ў выніку такога множання атрымліваецца лік больш за 9, яно замяняецца сумай лічбаў атрыманага множання — адной лічбай.
Усе атрыманыя ў выніку пераўтварэння лічбы складваюцца. Калі сума кратная 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;