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

Вступ

Алгоритм Луна, також відомий як "модуль 10" або "mod 10" алгоритм, є простим формулою контрольної суми, що використовується для перевірки різних ідентифікаційних номерів, таких як номери кредитних карток, канадські номери соціального страхування, номери IMEI та номери національного постачальника ідентифікаторів у Сполучених Штатах. Цей калькулятор дозволяє вам перевіряти номери за допомогою алгоритму Луна та генерувати дійсні номери, які проходять перевірку Луна.

Як працює алгоритм Луна

Алгоритм Луна працює наступним чином:

Починаючи з правого краю (виключаючи контрольну цифру) та рухаючись вліво, подвоюйте значення кожної другої цифри.
Якщо результат цієї операції подвоєння перевищує 9, відніміть 9 від результату.
Сумуйте всі цифри в отриманій послідовності.
Якщо загальна сума за модулем 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$ - це операція модуля.

Використання

Алгоритм Луна має різні застосування в різних сферах:

Перевірка кредитних карток: Більшість номерів кредитних карток перевіряються за допомогою алгоритму Луна.
Канадські номери соціального страхування: Алгоритм Луна використовується для перевірки дійсності цих ідентифікаційних номерів.
Номери IMEI: Номери IMEI мобільних телефонів містять контрольну цифру, перевірену за допомогою алгоритму Луна.
Номери національного постачальника ідентифікаторів (NPI): Використовуються в системі охорони здоров'я Сполучених Штатів, ці номери перевіряються за допомогою алгоритму Луна.
ISBN: Деякі номери ISBN-10 використовують варіант алгоритму Луна для перевірки.

Альтернативи

Хоча алгоритм Луна широко використовується, існують й інші алгоритми контрольних сум для різних цілей:

Алгоритм Дамма: Інший алгоритм контрольної цифри, який виявляє всі одноцифрові помилки та всі сусідні транспозиційні помилки.
Алгоритм Вергоффа: Більш складний алгоритм контрольної суми, який виявляє всі одноцифрові помилки та більшість транспозиційних помилок.
Контрольна цифра ISBN-13: Використовує інший алгоритм, ніж ISBN-10, який базується на алгоритмі Луна.

Історія

Алгоритм Луна був створений Гансом Петером Луном, комп'ютерним вченим IBM, у 1954 році. Лун був піонером у галузі інформаційних наук і має кілька нововведень, включаючи систему індексації KWIC (Key Word In Context).

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

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

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

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

import random

def luhn_validate(number):
    digits = [int(d) for d in str(number)]
    checksum = 0
    for i in range(len(digits) - 1, -1, -1):
        d = digits[i]
        if (len(digits) - i) % 2 == 0:
            d = d * 2
            if d > 9:
                d -= 9
        checksum += d
    return checksum % 10 == 0

def generate_valid_number(length):
    digits = [random.randint(0, 9) for _ in range(length - 1)]
    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
    check_digit = (10 - (checksum % 10)) % 10
    return int(''.join(map(str, digits + [check_digit])))

## Приклад використання:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Генерує дійсний 16-значний номер

function luhnValidate(number) {
    const digits = number.toString().split('').map(Number);
    let checksum = 0;
    for (let i = digits.length - 1; i >= 0; i--) {
        let d = digits[i];
        if ((digits.length - i) % 2 === 0) {
            d *= 2;
            if (d > 9) d -= 9;
        }
        checksum += d;
    }
    return checksum % 10 === 0;
}

function generateValidNumber(length) {
    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
    const checksum = digits.reduce((sum, digit, index) => {
        if ((length - 1 - index) % 2 === 0) {
            digit *= 2;
            if (digit > 9) digit -= 9;
        }
        return sum + digit;
    }, 0);
    const checkDigit = (10 - (checksum % 10)) % 10;
    return parseInt(digits.join('') + checkDigit);
}

// Приклад використання:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Генерує дійсний 16-значний номер

import java.util.Random;

public class LuhnValidator {
    public static boolean luhnValidate(long number) {
        String digits = String.valueOf(number);
        int checksum = 0;
        boolean isEven = true;
        for (int i = digits.length() - 1; i >= 0; i--) {
            int digit = Character.getNumericValue(digits.charAt(i));
            if (isEven) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
            isEven = !isEven;
        }
        return checksum % 10 == 0;
    }

    public static long generateValidNumber(int length) {
        Random random = new Random();
        long[] digits = new long[length - 1];
        for (int i = 0; i < length - 1; i++) {
            digits[i] = random.nextInt(10);
        }
        long checksum = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            long digit = digits[i];
            if ((length - 1 - i) % 2 == 0) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
        }
        long checkDigit = (10 - (checksum % 10)) % 10;
        long result = 0;
        for (long digit : digits) {
            result = result * 10 + digit;
        }
        return result * 10 + checkDigit;
    }

    public static void main(String[] args) {
        System.out.println(luhnValidate(4532015112830366L));  // true
        System.out.println(luhnValidate(4532015112830367L));  // false
        System.out.println(generateValidNumber(16));  // Генерує дійсний 16-значний номер
    }
}

Крайні випадки та спеціальні міркування

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

Перевірка вводу: Переконайтеся, що введення є дійсним числовим рядком. Нецифрові символи слід обробляти відповідно (або видаляти, або вважати недійсним ввідом).
Провідні нулі: Алгоритм повинен працювати правильно з номерами, що мають провідні нулі.
Великі числа: Будьте готові обробляти дуже довгі числа, які можуть перевищити ємність стандартних типів цілих чисел у деяких мовах програмування.
Порожній ввід: Визначте, як ваша реалізація повинна обробляти порожні рядки або null-вводи.
Нестандартні набори символів: У деяких застосуваннях ви можете зіткнутися з номерами, представленими символами поза стандартним діапазоном 0-9. Визначте, як їх слід обробляти.
Продуктивність: Для застосувань, які потребують швидкої перевірки великої кількості введень, розгляньте можливість оптимізації реалізації алгоритму.

Числові приклади

Дійсний номер кредитної картки:
- Номер: 4532015112830366
- Перевірка Луна: Дійсний
Недійсний номер кредитної картки:
- Номер: 4532015112830367
- Перевірка Луна: Недійсний
Дійсний канадський номер соціального страхування:
- Номер: 046 454 286
- Перевірка Луна: Дійсний
Недійсний номер IMEI:
- Номер: 490154203237518
- Перевірка Луна: Недійсний

Тестові випадки

Щоб перевірити реалізацію алгоритму Луна, ви можете використовувати наступні тестові випадки:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Тестування згенерованих номерів
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Усі тести пройдені!")

test_luhn_algorithm()

Посилання

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