Калкулатор на алгоритъма на Лун

Въведение

Алгоритъмът на Лун, известен също като "модул 10" или "mod 10" алгоритъм, е проста формула за контролна сума, използвана за валидиране на различни идентификационни номера, като номера на кредитни карти, канадски номера за социално осигуряване, IMEI номера и номера на национален доставчик на идентификатор в Съединените щати. Този калкулатор ви позволява да валидирате номера, използвайки алгоритъма на Лун, и да генерирате валидни номера, които преминават проверката на Лун.

Как работи алгоритъмът на Лун

Алгоритъмът на Лун работи по следния начин:

1. Започвайки от най-дясната цифра (с изключение на контролната цифра) и преминавайки наляво, удвоете стойността на всяка втора цифра.
2. Ако резултатът от операцията по удвояване е по-голям от 9, извадете 9 от резултата.
3. Сумирайте всички цифри в получената последователност.
4. Ако общата сума модул 10 е равна на 0 (ако общата сума завършва на нула), тогава номерът е валиден според формулата на Лун; в противен случай не е валиден.

Ето визуално представяне на алгоритъма на Лун:

Формула

Алгоритъмът на Лун може да бъде изразен математически, както следва:

Нека $d_i$ бъде $i$-та цифра, броейки от най-дясната цифра (с изключение на контролната цифра) и преминавайки наляво. Тогава контролната цифра $d_0$ е избрана така, че:

$(2d_{2n} \bmod 9 + d_{2n-1} + 2d_{2n-2} \bmod 9 + d_{2n-3} + \cdots + 2d_2 \bmod 9 + d_1 + d_0) \bmod 10 = 0$

Където $\bmod$ е операцията модул.

Приложения

Алгоритъмът на Лун има различни приложения в различни области:

1. Валидиране на кредитни карти: Повечето номера на кредитни карти се валидират с помощта на алгоритъма на Лун.
2. Канадски номера за социално осигуряване: Алгоритъмът на Лун се използва за проверка на валидността на тези идентификационни номера.
3. IMEI номера: Номерата на мобилни телефони IMEI включват контролна цифра, валидирана от алгоритъма на Лун.
4. Номера на национален доставчик на идентификатор (NPI): Използвани в системата на здравеопазването в Съединените щати, тези номера се валидират с помощта на алгоритъма на Лун.
5. ISBN: Някои номера ISBN-10 използват вариант на алгоритъма на Лун за валидиране.

Алтернативи

Докато алгоритъмът на Лун е широко използван, съществуват и други алгоритми за контролна сума за различни цели:

1. Алгоритъм на Дам: Друг алгоритъм за контролна цифра, който открива всички единични грешки и всички съседни транспозиционни грешки.
2. Алгоритъм на Верхофф: По-сложен алгоритъм за контролна сума, който улавя всички единични грешки и повечето транспозиционни грешки.
3. Контролна цифра ISBN-13: Използва различен алгоритъм от ISBN-10, който е базиран на алгоритъма на Лун.

История

Алгоритъмът на Лун е създаден от Ханс Петер Лун, компютърен учен от IBM, през 1954 година. Лун е пионер в областта на информационната наука и е кредитирани с няколко иновации, включително системата за индексиране KWIC (Ключова дума в контекста).

Алгоритъмът първоначално е проектиран да защитава срещу случайни грешки, а не срещу злонамерени атаки. Важно е да се отбележи, че докато алгоритъмът на Лун може да открие много общи грешки, той не е сигурна форма на криптиране и не трябва да се разчита за цели по сигурността на данните.

Въпреки възрастта си, алгоритъмът на Лун остава широко използван поради своята простота и ефективност при улавяне на общи грешки при транскрипция.

Примери за имплементация

Ето някои примери за код за имплементиране на алгоритъма на Лун на различни програмни езици:

1import random
2
3def luhn_validate(number):
4    digits = [int(d) for d in str(number)]
5    checksum = 0
6    for i in range(len(digits) - 1, -1, -1):
7        d = digits[i]
8        if (len(digits) - i) % 2 == 0:
9            d = d * 2
10            if d > 9:
11                d -= 9
12        checksum += d
13    return checksum % 10 == 0
14
15def generate_valid_number(length):
16    digits = [random.randint(0, 9) for _ in range(length - 1)]
17    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
18    check_digit = (10 - (checksum % 10)) % 10
19    return int(''.join(map(str, digits + [check_digit])))
20
21## Пример за употреба:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Генерира валиден 16-цифрен номер
25

1function luhnValidate(number) {
2    const digits = number.toString().split('').map(Number);
3    let checksum = 0;
4    for (let i = digits.length - 1; i >= 0; i--) {
5        let d = digits[i];
6        if ((digits.length - i) % 2 === 0) {
7            d *= 2;
8            if (d > 9) d -= 9;
9        }
10        checksum += d;
11    }
12    return checksum % 10 === 0;
13}
14
15function generateValidNumber(length) {
16    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
17    const checksum = digits.reduce((sum, digit, index) => {
18        if ((length - 1 - index) % 2 === 0) {
19            digit *= 2;
20            if (digit > 9) digit -= 9;
21        }
22        return sum + digit;
23    }, 0);
24    const checkDigit = (10 - (checksum % 10)) % 10;
25    return parseInt(digits.join('') + checkDigit);
26}
27
28// Пример за употреба:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Генерира валиден 16-цифрен номер
32

1import java.util.Random;
2
3public class LuhnValidator {
4    public static boolean luhnValidate(long number) {
5        String digits = String.valueOf(number);
6        int checksum = 0;
7        boolean isEven = true;
8        for (int i = digits.length() - 1; i >= 0; i--) {
9            int digit = Character.getNumericValue(digits.charAt(i));
10            if (isEven) {
11                digit *= 2;
12                if (digit > 9) digit -= 9;
13            }
14            checksum += digit;
15            isEven = !isEven;
16        }
17        return checksum % 10 == 0;
18    }
19
20    public static long generateValidNumber(int length) {
21        Random random = new Random();
22        long[] digits = new long[length - 1];
23        for (int i = 0; i < length - 1; i++) {
24            digits[i] = random.nextInt(10);
25        }
26        long checksum = 0;
27        for (int i = digits.length - 1; i >= 0; i--) {
28            long digit = digits[i];
29            if ((length - 1 - i) % 2 == 0) {
30                digit *= 2;
31                if (digit > 9) digit -= 9;
32            }
33            checksum += digit;
34        }
35        long checkDigit = (10 - (checksum % 10)) % 10;
36        long result = 0;
37        for (long digit : digits) {
38            result = result * 10 + digit;
39        }
40        return result * 10 + checkDigit;
41    }
42
43    public static void main(String[] args) {
44        System.out.println(luhnValidate(4532015112830366L));  // true
45        System.out.println(luhnValidate(4532015112830367L));  // false
46        System.out.println(generateValidNumber(16));  // Генерира валиден 16-цифрен номер
47    }
48}
49

Гранични случаи и специални съображения

При имплементирането на алгоритъма на Лун, вземете предвид следните гранични случаи и специални съображения:

1. Проверка на входа: Уверете се, че входът е валиден числов низ. Неподходящите символи трябва да се обработват подходящо (или да се премахнат, или да се третират като невалиден вход).

2. Водещи нули: Алгоритъмът трябва да работи правилно с номера, които имат водещи нули.

3. Големи числа: Бъдете готови да обработвате много дълги числа, които може да надвишават капацитета на стандартните цели числа в някои програмни езици.

4. Празен вход: Определете как вашата имплементация трябва да обработва празни низове или нулеви входове.

5. Нестандартни набори от символи: В някои приложения може да срещнете номера, представени с символи извън стандартния диапазон 0-9. Определете как тези трябва да се обработват.

6. Производителност: За приложения, които трябва да валидират голям брой входове бързо, обмислете оптимизиране на имплементацията на алгоритъма.

Числови примери

1. Валиден номер на кредитна карта:

   • Номер: 4532015112830366
   • Проверка на Лун: Валиден

2. Невалиден номер на кредитна карта:

   • Номер: 4532015112830367
   • Проверка на Лун: Невалиден

3. Валиден канадски номер за социално осигуряване:

   • Номер: 046 454 286
   • Проверка на Лун: Валиден

4. Невалиден IMEI номер:

   • Номер: 490154203237518
   • Проверка на Лун: Невалиден

Тестови случаи

За да проверите имплементацията на алгоритъма на Лун, можете да използвате следните тестови случаи:

1def test_luhn_algorithm():
2    assert luhn_validate(4532015112830366) == True
3    assert luhn_validate(4532015112830367) == False
4    assert luhn_validate(79927398713) == True
5    assert luhn_validate(79927398714) == False
6    
7    # Тест на генерирани номера
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("Всички тестове преминаха успешно!")
12
13test_luhn_algorithm()
14

Референции

1. Лун, Х. П. (1960). "Компютър за проверка на номера". Патент на САЩ 2,950,048.
2. Галиан, Джоузеф. "Математиката на идентификационните номера." Колежански математически журнал, т. 22, № 3, 1991, стр. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Международна организация по стандартизация. Изтеглено на 2 август 2024 г.
4. Кнут, Доналд. "Изкуството на компютърното програмиране, том 2: Семинумерични алгоритми". Addison-Wesley, 1997.