Калькулятор алгоритму Луна - Перевірка кредитних карток та IMEI

Розуміння алгоритму Луна

Потрібно перевірити номер кредитної картки або підтвердити IMEI? Алгоритм Луна (або "алгоритм mod 10") - це формула контрольної суми, яка є основою перевірки платежів з 1954 року. Вчений IBM Ганс Петер Лун розробив цей елегантний математичний метод перевірки, щоб виявляти помилки друку та транскрипції, які виникають при ручному введенні даних — наприклад, коли ви випадково міняєте місцями два цифри або неправильно вводите одну цифру.

Ось що робить його незамінним: кожна провідна платіжна мережа (Visa, Mastercard, American Express), номери мобільних пристроїв IMEI, канадські номери соціального страхування та ідентифікатори постачальників медичних послуг США покладаються на цей алгоритм. Коли ви вводите номер картки у платіжну форму, і вона миттєво відхиляє помилку, це і є перевірка Луна в дії.

Цей калькулятор дозволяє перевіряти будь-яку послідовність цифр або генерувати тестові дані, які проходять перевірку — це важливо при створенні платіжних інтеграцій або тестуванні систем ідентифікації без використання реальних даних клієнтів.

Як використовувати цей калькулятор

Перевірка наявних номерів: Введіть будь-яку послідовність цифр — наприклад, 16-значний номер кредитної картки або 15-значний IMEI — і натисніть "Перевірити". Ви одразу побачите, чи проходить він перевірку за модулем 10, а також покроковий опис того, як оброблялася кожна цифра. Це особливо корисно при налагодженні форм оплати або перевірці точності введення даних.

Генерування тестових даних: Перейдіть до режиму "Генерація", щоб створити дійсні тестові номери будь-якої довжини. Ці номери проходять перевірку Луна, але не є реальними активними картками — що робить їх ідеальними для середовищ розробки, де потрібні реалістичні тестові випадки без використання реальних платіжних даних.

Розуміння процесу: Візуалізація показує точно, що відбувається з кожною цифрою: які подвоюються, коли віднімається 9, і як остаточна сума визначає дійсність. Я знайшов цей візуальний зворотний зв'язок неоціненним при поясненні алгоритму колегам або налагодженні впровадження.

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

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

1. Почніть справа: Беріть кожну цифру, рухаючись ліворуч. Кожна друга цифра подвоюється (це ті, що знаходяться в парних позиціях при підрахунку справа).

2. Обробка великих подвоєнь: Коли подвоєння призводить до числа більше 9, віднімайте 9. Це математично еквівалентно додаванню окремих цифр (18 стає 1+8=9).

3. Підсумуйте все: Додайте всі оброблені цифри — як подвоєні/скориговані, так і незмінені.

4. Перевірте подільність: Якщо сума ділиться без залишку на 10 (закінчується на 0), число є дійсним. Будь-який інший результат означає наявність помилки.

Геніальність цього підходу полягає в тому, як він виявляє поширені помилки. Якщо ви поміняли місцями дві суміжні цифри або неправильно ввели одну цифру, контрольна сума майже завжди зміниться. Алгоритм не виявить кожну можливу помилку — подвійні помилки, такі як заміна 22 на 55, проходять непоміченими — але він виявляє приблизно 98% випадкових однозначних помилок і близько 90% суміжних перестановок.

Ось наочне представлення процесу:

Математична формула

Для тих, хто надає перевагу формальній нотації, ось математичний вираз:

Нехай $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$ є операцією взяття за модулем.

Реальні застосування

Обробка платежів: Кожна провідна платіжна система — Visa, Mastercard, American Express, Discover — використовує перевірку Луна як перший рубіж захисту від друкарських помилок. Під час створення форми оплати, впровадження клієнтської перевірки Луна допомагає користувачам уникнути надсилання очевидно неправильних номерів і зменшує непотрібні API-виклики до платіжних шлюзів.

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

Ідентифікатори охорони здоров'я: Система National Provider Identifier (NPI) США перевіряє номери постачальників за допомогою цього алгоритму. З мільйонами щоденних медичних транзакцій виявлення помилок при переписуванні в ідентифікаторах постачальників запобігає затримкам у виставленні рахунків і зменшує відхилення претензій.

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

Системи обліку книг: Деякі реалізації ISBN-10 використовують варіант Луна. Хоча ISBN-13 використовує інший алгоритм контрольної цифри, старі бібліотечні та інвентарні системи все ще покладаються на перевірку на основі Луна.

Покрокові приклади

Перевірка номера кредитної картки

Перевірмо номер 4532015112830366:

1. Починаючи справа: 6, 6, 3, 0, 3, 8, 2, 1, 1, 5, 1, 0, 2, 3, 5, 4
2. Подвоїти кожну другу цифру (справа): 6, 12, 3, 0, 3, 16, 2, 2, 1, 10, 1, 0, 2, 6, 5, 8
3. Відняти 9 від чисел > 9: 6, 3, 3, 0, 3, 7, 2, 2, 1, 1, 1, 0, 2, 6, 5, 8
4. Сума: 6+3+3+0+3+7+2+2+1+1+1+0+2+6+5+8 = 50
5. 50 % 10 = 0 ✓ Дійсний!

Виявлення невірного IMEI-номера

Перевірка 490154203237518 (останню цифру навмисно змінено):

1. Після подвоєння та обробки: Сума = 57
2. 57 % 10 = 7 ✗ Недійсний!

Сума не закінчується на нуль, тому алгоритм позначає його як невірний. Щоб зробити його дійсним, остання цифра повинна бути 1, що призведе суму до 60 — ідеально поділеної на 10. Саме так алгоритм виявляє помилки при введенні ідентифікаторів пристроїв.

Альтернативні алгоритми контрольної суми

Алгоритм Луна популярний через простоту реалізації, але існують більш витончені альтернативи, коли потрібне надійніше виявлення помилок:

Алгоритм Верхоффа: Виявляє всі однозначні помилки та майже всі помилки транспозиції, включаючи випадки подвійних цифр, які пропускає алгоритм Луна (наприклад, 22↔55). Компроміс полягає в підвищеній складності — потребує таблиць пошуку з операціями множення та перестановки. Використовуйте його, коли точність даних критична, а обчислювальне навантаження не має значення.

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

Контрольна цифра ISBN-13: Використовує зважений алгоритм за модулем 10, відмінний від Луна та ISBN-10. Ваги чергуються між 1 і 3, що забезпечує хороше виявлення помилок для ідентифікаторів книг. Це замінило старішу систему ISBN-10 (яка використовувала алгоритм Луна), коли галузі знадобився більший простір ідентифікаторів.

Історія та контекст

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

Ось принципова відмінність: Лун розробив це для виявлення помилок, а не безпеки. У 1950-х роках проблемою були помилки перфокарт та помилки ручного введення, а не цифрове шахрайство. Алгоритм чудово виявляє випадкові друкарські помилки — але це не криптографія. Дійсний номер Луна не означає, що картка активна, фінансована або належить особі, яка її використовує.

Дивовижно, наскільки добре 70-річний алгоритм досі виконує свою первісну мету. Платіжні процесори нашаровують сучасні засоби безпеки (токенізацію, перевірку CVV, 3D Secure), але той initial клієнтський контроль Луна все ще щодня зупиняє мільйони очевидних помилок до того, як вони витратять пропускну здатність на виклики платіжного шлюзу.

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

Ось як реалізувати перевірку та генерацію за алгоритмом Луна в Python, JavaScript та Java. Ці приклади орієнтовані на читабельність при збереженні ефективності:

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## Приклад використання:
22
23print(luhn_validate(4532015112830366))  # True
24print(luhn_validate(4532015112830367))  # False
25print(generate_valid_number(16))  # Генерує коректний 16-значний номер
26

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

Крайні випадки та особливості реалізації

При впровадженні перевірки за алгоритмом Луна у виробничих системах зверніть увагу на такі поширені проблеми:

Санітарна обробка вхідних даних: Реальні вхідні дані часто містять пробіли, дефіси або інші форматуючі символи (наприклад, "4532-0151-1128-3036"). Видаляйте їх перед перевіркою, а не відхиляйте введення — користувачі часто копіюють форматовані номери. Однак негайно відхиляйте алфавітні символи, оскільки вони вказують на дійсно неправильний ввід.

Провідні нулі мають значення: Число на кшталт "0123456789" відрізняється від "123456789" з точки зору алгоритму Луна. Провідні нулі мають бути збережені під час перевірки. Це заплутує розробників, які спочатку перетворюють на цілі числа — використовуйте натомість строкові операції.

Обмеження цілих чисел у мові: Кредитні картки зазвичай мають максимум 19 цифр, що вміщуються в 64-бітне ціле число. Але якщо ви перевіряєте ідентифікатори довільної довжини, уникайте перетворення на цілі числа взагалі. Обробляйте як рядки або масиви цифр, щоб запобігти переповненню.

Порожній або нульовий ввід: Чітко визначте свою поведінку: викинути виняток, повернути хибне значення або обробити коректно? Я з'ясував, що найбільш логічно повертати хибне значення для функцій перевірки, хоча кінцеві точки API можуть бажати повернути помилку 400 з описовим повідомленням.

Продуктивність у масштабі: Для пакетної перевірки (наприклад, обробки завантажених CSV-файлів з тисячами номерів карток) базовий алгоритм і так досить швидкий — O(n), де n — кількість цифр. Вузьким місцем зазвичай є введення-виведення, а не обчислення. Зосередьте оптимізацію на аналізі файлів та звітуванні про помилки, а не на логіці перевірки.

Швидкий довідник: Тестові числа

Використовуйте їх для перевірки вашої реалізації:

Коректні числа:

• 4532015112830366 — Формат Visa (16 цифр)
• 046454286 — Формат канадського SIN (9 цифр)
• 79927398713 — Загальний коректний номер

Некоректні числа:

• 4532015112830367 — Помилка на одну цифру
• 490154203237518 — Невірна контрольна цифра
• 79927398714 — Остання цифра невірна

Ці тестові випадки охоплюють поширені сценарії: стандартні коректні числа, помилки на одну цифру та невірні контрольні цифри.

Автоматизований Набір Тестів

Ось повний набір тестів для перевірки вашої реалізації:

1def test_luhn_algorithm():
2    # Базові тести перевірки
3    assert luhn_validate(4532015112830366) == True
4    assert luhn_validate(4532015112830367) == False
5    assert luhn_validate(79927398713) == True
6    assert luhn_validate(79927398714) == False
7
8    # Перевірка згенерованих номерів на валідність
9    for _ in range(10):
10        generated = generate_valid_number(16)
11        assert luhn_validate(generated) == True, f"Згенерований {generated} не пройшов перевірку"
12
13    # Крайній випадок: одна цифра
14    assert luhn_validate(0) == True  # 0 mod 10 = 0
15
16    # Крайній випадок: збереження провідних нулів
17    assert luhn_validate("0000000000000000") != luhn_validate(0)
18
19    print("Всі тести пройдено!")
20
21test_luhn_algorithm()
22

Часто запитувані питання

Для чого використовується алгоритм Луна?

Алгоритм Луна перевіряє ідентифікаційні номери, включаючи кредитні картки (Visa, Mastercard, Amex), IMEI-номери мобільних пристроїв, канадські соціальні страхові номери та медичні NPI-номери США. Він виявляє поширені помилки введення даних — наприклад, неправильно введені цифри або випадково переставлені числа — перед тим, як вони спричинять помилки обробки або невдалі транзакції.

Наскільки точно алгоритм Луна виявляє помилки?

Алгоритм Луна виявляє приблизно 98% помилок з однією цифрою та близько 90% помилок суміжної перестановки (наприклад, введення "12" замість "21"). Однак він пропускає подвійні помилки, коли обидві цифри однакові (22→55) та стрибкоподібні перестановки (101→404). Для більшості практичних застосувань, пов'язаних з ручним введенням даних, цей рівень виявлення є достатнім.

Чи можна перевірити кредитні картки офлайн за допомогою алгоритму Луна?

Так, перевірка Луна працює повністю офлайн — це чиста математика, яка не вимагає пошуку в базі даних або викликів API. Це робить її ідеальною для перевірки на стороні клієнта у веб-формах, зменшуючи навантаження на сервер і надаючи миттєвий зворотний зв'язок користувачам. Але пам'ятайте: дійсний номер за Луна не означає, що картка активна або має доступний кредит.

Чи є алгоритм Луна безпечним для обробки платежів?

Ні — Луна призначений для виявлення помилок, а не забезпечення безпеки. Він перевіряє лише математичний формат. Проходження перевірки Луна не підтверджує, що картка реальна, активна, профінансована або належить користувачеві. Сучасна безпека платежів вимагає кількох рівнів: перевірки CVV/CVC, перевірки адреси (AVS), автентифікації 3D Secure та токенізації. Луна — лише перша перевірка коректності.

Які мови програмування підтримують реалізацію Луна?

Кожна загальна мова програмування може реалізувати Луна — це простий алгоритм, що вимагає лише базової арифметики та циклів. Python, JavaScript, Java, C++, C#, PHP, Ruby, Go, Rust та Swift легко справляються з ним за 10-20 рядків коду. Деякі мови мають сторонні бібліотеки, але алгоритм досить простий, щоб більшість розробників реалізували його безпосередньо.

Чому його називають алгоритмом mod 10?

Останній крок перевіряє, чи сума цифр ділиться на 10 з використанням операції модуло (sum % 10 == 0). "Mod 10" стосується саме цієї перевірки за модулем 10. Якщо залишок дорівнює нулю при діленні на 10, номер проходить — інакше він не проходить. Ця математична властивість і робить алгоритм працездатним.

Чи можна генерувати тестові номери кредитних карток за допомогою Луна?

Так — ви можете генерувати номери, які проходять перевірку Луна для тестування форм оплати під час розробки. Це не реальні, активні картки; вони просто задовольняють математичний формат. Це легально і необхідно для тестування, але спроба використати згенеровані номери для реальних покупок є шахрайством. Більшість платіжних шлюзів пропонують офіційні тестові номери карток для середовищ розробки.

Які обмеження алгоритму Луна?

Луна не виявляє: подвійні помилки (22↔55), стрибкоподібні перестановки (101↔404), фонетичні помилки (60↔06 у деяких випадках) або кілька одночасних помилок. Він також не забезпечує криптографічної безпеки — дійсний формат не означає дійсну картку. Незважаючи на ці обмеження, його простота та рівень виявлення помилок понад 90% роблять його практичним для реальних платіжних систем у поєднанні з іншими методами перевірки.

Почніть перевірку номерів

Використовуйте калькулятор вище для перевірки номерів кредитних карток, генерації тестових даних для середовищ розробки або вивчення того, як алгоритм mod 10 обробляє кожну цифру. Покрокова візуалізація допомагає налагодити проблеми з реалізацією та пояснити результати перевірки нетехнічним учасникам проекту.

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

Посилання та додаткова література

1. Люн, Г. П. (1960). "Комп'ютер для перевірки чисел". Патент США 2,950,048 - Оригінальний патент, що описує алгоритм.

2. ISO/IEC 7812-1:2017 - Ідентифікаційні картки - Міжнародний стандарт для систем нумерації ідентифікаційних карток, який визначає використання алгоритму Люна для платіжних карток.

3. Галліан, Джозеф (1991). "Математика ідентифікаційних номерів" - Академічний аналіз різних алгоритмів контрольних цифр, включаючи алгоритм Люна, опублікований у журналі "The College Mathematics Journal".

4. Стандарт безпеки даних індустрії платіжних карток (PCI DSS) - Стандарти безпеки, що регулюють поводження з даними платіжних карток, надаючи контекст місця алгоритму Люна в стеку безпеки.