Лунов алгоритам

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Lunov algoritam ili Lunova formula, takođe poznat i kao "modul 10" ili "mod 10" algoritam, je algoritam koji koristi kontrolnu sumu za potvrdu raznih identifikacionih brojeva, kao što su brojevi kreditne kartice, IMEI brojevi i brojevi zdravstvenog osiguranja u Kanadi. Razvio ga je naučnik zaposlen u IBM-u Hans Piter Lun (engl. Hans Peter Luhn), захтев за патент је поднет 6. јануара 1954. и патент је одобрен 23. августа 1960. године и заведен као У.С. Патент Но. 2,950,048

Алгоритам је јавно власништво и данас је у широкој употреби. Одређен је стандардом ИСО/ИЕЦ 7812-1.^[1] Није намеравано да алгоритам буде криптографска функција за сажимање већ заштита од случајних грешака, а не од злонамерних напада. Већина кредитних картица као и многи владини идентификациони бројеви користе овај алгоритам као једноставну методу за разликовање валидних бројева од погрешно откуцаних или нетачних бројева.

Опис[уреди | уреди извор]

Овај алгоритам верификује исправност броја помоћу контролне цифре која је укључена у сам број и која се обично надовезује на непотпун број рачуна чиме се добије потпун број рачуна. Број рачуна мора проћи следећи тест:

Почевши од крајње десне цифре, која је контролна цифра, крећући се налево, удвостручити вредност сваке друге цифре; ако је тај производ већи од 9 (нпр. 8 × 2 = 16), тада сабрати цифре производа (нпр. 16: 1 + 6 = 7, 18: 1 + 8 = 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	-
Збир цифара	7	9	9	4	7	6	9	7	7	2	=67

Контролна цифра (x) се добија израчунавањем суме цифара, затим множењем са 9 и израчунавањем остатка при дељењу са 10 (математички записано, (67 × 9 мод 10)). Алгоритамски представљено:

Израчунати суму свих цифара (67).
Помножити са 9 (603).
Последња цифра, 3, је контролна цифра. Одатле, x=3.

(Алтернативна метода) Контролна цифра (x) добија се израчунавањем суме цифара а затим одузимањем цифре јединице од 10 (67 = цифра јединице 7; 10 − 7 = контролна цифра 3). Алгоритамски представљено:

Израчунати збир цифара (67).
Узети цифру јединице (7).
Одузети цифру јединице од 10.
Резултат (3) је контролна цифра. У случају да се сума цифара завршава нулом, 0 је контролна цифра.

Одатле је потпун број рачуна 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).

Поред тога, Лунов алгоритам не проверава да ли је дужина броја валидна. На пример, посматрајмо валидан број кредитне картице "5578249275041923" који садржи 16 цифара. Када изоставимо последње три цифре добијамо неисправан број "5578249275041" који пролази валидацију Луновим алгоритмом (на начин описан раније). Такође Лунов алгоритам не може утврдити о ком типу картице је реч. Наиме, уколико посматрамо валидан број кредитне картице, као што је "5397373822153004", прве две цифре означавају да се ради о МастерЦард картици, када променимо прве две цифре добијамо број "4697373822153004" где нам сада прве две цифре означавају да се ради о Виса картици. Број ће такође проћи Лунову валидацију али овај број Виса картице није валидан. У вези са тим, предложена су побољшања алгоритма тако што се имплементира провера дужина броја кредитне картице као и провера типа кредитне картице.^[2]

Остали, сложенији алгоритми за проверу исправности (као што су Верхоефов алгоритам као и Дамов алгоритам), могу детектовати више грешака у куцању. Лунов мод Н алгоритам је проширење које подржава и ненумеричке ниске.

Пошто се алгоритам извршава слева надесно и нуле утичу на резултата само ако узрокују промену позиције осталих цифара, нула на почетку ниске не утиче на израчунавање. Одатле системи који надовезују нуле да би број садржао одређени број цифара (који конвертују нпр. 1234 у 0001234) могу да извршавају Лунову валидацију пре или након надовезивања.

Надовезивање нуле на почетак броја непарне дужине нам омогућава да обрађујемо број здесна налево при чему удвостручујемо цифре на непарним местима.

Алгоритам је првобитно патентиран за ручну механичку направу која је израчунавала контролне цифре. Стога је морао бити прилично једноставан. Направа је израчунавала остатак при дељењу са 10 на механички начин. Цифре за замену, односно, резултати дуплирања и одузимања, нису добијани на механички начин. Уместо тога, цифре су уписане у пермутованом редоследу на самој направи.

Имплементација мод 10 алгоритма[уреди | уреди извор]

Имплементације које следе написане су у програмском језику Пyтхон.

Верификација контролне цифре[уреди | уреди извор]

def luhn_checksum(card_number):
    def digits_of(n):
        return [int(d) for d in str(n)]
    digits = digits_of(card_number)
    odd_digits = digits[-1::-2]
    even_digits = digits[-2::-2]
    checksum = 0
    checksum += sum(odd_digits)
    for d in even_digits:
        checksum += sum(digits_of(d*2))
    return checksum % 10

def is_luhn_valid(card_number):
    return luhn_checksum(card_number) == 0

Израчунавање контролне цифре[уреди | уреди извор]

Алгоритам изнад проверава исправност улаза помоћу контролне цифре. Израчунавање контролне цифре захтева само мању измену алгоритма на следећи начин:

Надовезати нулу као контролну цифру непотпуном броју и затим израчунати контролну суму
Ако је (сума мод 10) == 0, тада је контролна цифра 0
Иначе, контролна цифра = 10 - (сума мод 10)

def calculate_luhn(partial_card_number):
    check_digit = luhn_checksum(int(partial_card_number) * 10)
    return check_digit if check_digit == 0 else 10 - check_digit

Закључак[уреди | уреди извор]

Лунов алгоритам је широко распрострањен, нарочито се интензивно користи на интернету за валидацију бројева кредитних картица, међутим овај алгоритам има озбиљних слабости. Предложено је више проширења оригиналног алгоритма које те слабости делимично решавају.

Референце[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]

[1] ИСО/ИЕЦ 7812-1:2006 Идентифицатион цардс -- Идентифицатион оф иссуерс -- Парт 1: Нумберинг сyстем

[2] Јоурнал: Интернатионал Јоурнал оф Цомпутер Сциенце анд Мобиле Цомпутинг - ИЈЦСМЦ (Вол.2, Но. 7), Кхалид Wалеед Хуссеин; Др. Нор Фазлида Мохд. Сани; Профессор Др. Рамлан Махмод; Др. Мохд. Тауфик Абдуллах, 2013-07-30

[1]

[2]