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

Введение

Алгоритм Луна, также известный как алгоритм "модуль 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. Пустой ввод: Определите, как ваша реализация должна обрабатывать пустые строки или нулевые входные данные.

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.