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

Вступ

Алгоритм Луна, також відомий як "модуль 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 (Key Word In Context).

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

Незважаючи на свій вік, алгоритм Луна залишається широко використовуваним завдяки своїй простоті та ефективності у виявленні загальних помилок транскрипції.

Приклади реалізації

Ось кілька прикладів коду для реалізації алгоритму Луна на різних мовах програмування:

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. Порожній ввід: Визначте, як ваша реалізація повинна обробляти порожні рядки або null-вводи.

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.