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

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

Въведение

Алгоритъмът на Лун, известен също като "модул 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 (Ключова дума в контекста).

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

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

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

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

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-цифрен номер
    }
}

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

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

Проверка на входа: Уверете се, че входът е валиден числов низ. Неподходящите символи трябва да се обработват подходящо (или да се премахнат, или да се третират като невалиден вход).
Водещи нули: Алгоритъмът трябва да работи правилно с номера, които имат водещи нули.
Големи числа: Бъдете готови да обработвате много дълги числа, които може да надвишават капацитета на стандартните цели числа в някои програмни езици.
Празен вход: Определете как вашата имплементация трябва да обработва празни низове или нулеви входове.
Нестандартни набори от символи: В някои приложения може да срещнете номера, представени с символи извън стандартния диапазон 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.