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

З Вікіпедыі, свабоднай энцыклапедыі

Алгарытм Лу́на (англ.: 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;

Аналагі[правіць | правіць зыходнік]

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

Літаратура[правіць | правіць зыходнік]

Спасылкі[правіць | правіць зыходнік]