Вікіпедыя

Алгарытм Луна

Алгарытм Лу́на (англ.: Luhn algorithm), або формула Луна, або алгарытм Мод10 — алгарытм вылічэння кантрольнага ліку нумара пластыкавых картак у адпаведнасці са стандартам ISO/IEC 7812. Не з'яўляецца крыптаграфічным сродкам, прызначэнне алгарытму ў першую чаргу - выяўленне памылак, выкліканых ненаўмысным скажэннем даных (напрыклад, пры ручным уводзе нумара карткі, пры прыёме даных аб нумары сацыяльнага страхавання праз тэлефон). Дазваляе толькі з некаторай ступенню пэўнасці судзіць аб адсутнасці памылак у блоку лікаў, але не дае магчымасці лакалізацыі і карэкцыі выяўленай недакладнасці.

Алгарытм распрацаваны супрацоўнікам фірмы IBM Гансам Пітэрам Лунам  (англ.) (бел., апісаны ў ЗША ў 1954 годзе, патэнт атрыманы ў 1960 годзе.

Найбольш распаўсюджаныя ўжыванні для падліку кантрольнга ліку:

  • Нумары ўсіх банкаўскіх картак
  • Нумары некаторых дысконтных картак
  • Коды сацыяльнага страхавання
  • IMEI - коды.
  • Разлік кантрольнага знака адзінага 8-значнага нумара чыгуначнага вагона на Расійскай чыгунцы.

У цяперашні час змест алгарытму з'яўляецца грамадскім здабыткам.

Перавагі і недахопы правіць

У сілу прастаты рэалізацыі, алгарытм спажывае мінімум вылічальных магутнасцяў; у шэрагу выпадкаў пры наяўнасці навыка разлік можа быць выкананы ў уме. У той жа час, алгарытм Луна дазваляе толькі выявіць памылкі ў блоках даных, і нават не ўсе. Скажэнне адной лічбы выяўляецца. ВЫяўляюцца амаль усе парныя перастаноўкі лічбаў, якія ідуць запар (за выключэннем 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, то зыходны радок правільны.

Рэалізацыя алгарытму правіць

C правіць

На ўваходзе функцыі: масіў 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);
}

JS правіць

На ўваходзе функцыі: масіў 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))
}

Java правіць

На ўваходзе функцыі: масіў 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;
    }
}

Pascal правіць 

 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;

Аналагі правіць

Алгарытм Верхуфа

Літаратура правіць

Спасылкі правіць

Узята з "https://be.wikipedia.org/w/index.php?title=Алгарытм_Луна&oldid=4033299"