Тайна последней цифры карты: как алгоритм Луна ловит опечатки

Последняя цифра номера вашей карты не случайна — это сторож, вычисленный из всех остальных цифр.

Контрольная цифра не защищает от мошенника, но ловит честную опечатку — и экономит миллионы бессмысленных запросов к банкам.

Наберите номер банковской карты, ошибившись в одной цифре, — и форма оплаты подсветит ошибку ещё до отправки. Откуда сайт знает, что номер «битый», не зная вашего банка? Секрет в том, что номер карты несёт в себе встроенную проверку — благодаря алгоритму Луна, который запатентовал инженер IBM Ганс Петер Лун в 1954 году.

Что такое контрольная цифра

Последняя цифра номера карты — особая. Она не часть «адреса» счёта, а контрольная сумма, вычисленная из всех предыдущих цифр по строгому правилу. Если переписать номер с ошибкой, контрольная цифра почти наверняка перестанет сходиться с остальными — и проверка это поймает.

Та же идея работает в штрихкодах, ISBN книг и номерах счетов. Везде последний знак — это математический «замок», подтверждающий целостность.

Как считается алгоритм Луна

Правило на удивление простое. Идём по цифрам номера справа налево:

1. Каждую вторую цифру (начиная со второй справа) удваиваем.
2. Если при удвоении получилось число больше $9$ — вычитаем из него $9$ (или, что то же, складываем его цифры).
3. Складываем все получившиеся цифры в одну сумму.
4. Если сумма делится на $10$ без остатка — номер прошёл проверку.

Условие корректности записывается так:

$$S \equiv 0 \pmod{10}$$

где $S$ — итоговая сумма. Контрольная цифра как раз и подбирается заранее так, чтобы это равенство выполнялось.

Разберём на маленьком примере

Проверим короткий номер $7992739871$. Удваиваем каждую вторую цифру справа, при необходимости вычитаем $9$, складываем всё вместе — и получаем сумму, кратную $10$. Значит, номер «честный»: ни одна цифра не переврана. Подмените любую одну — и сумма перестанет делиться на $10$.

def luhn_ok(number):
    digits = [int(d) for d in str(number)][::-1]
    total = 0
    for i, d in enumerate(digits):
        if i % 2 == 1:      # каждая вторая цифра справа
            d = d * 2
            if d > 9:
                d -= 9
        total += d
    return total % 10 == 0

print(luhn_ok("79927398713"))  # True
print(luhn_ok("79927398714"))  # False

Что Лун ловит, а что — нет

Алгоритм отлично отлавливает две самые частые человеческие ошибки: одиночную опечатку в любой цифре и перестановку соседних цифр (когда вместо «...34...» вы набрали «...43...»). Именно так чаще всего и ошибаются люди, переписывая длинные номера.

Почему именно умножение на два

Может показаться, что удвоение каждой второй цифры взято с потолка, но в нём вся соль. Если бы алгоритм просто складывал все цифры, он не заметил бы перестановку соседей: сумма $3+4$ и $4+3$ одинакова. А вот когда одну из цифр удваивают, а другую нет, их вклады становятся разными — и перестановка тут же ломает контрольную сумму. Вычитание девятки при переполнении сохраняет красивое свойство: результат по-прежнему укладывается в одну цифру и остаётся согласованным по модулю $10$. Простая на вид процедура на самом деле тонко подобрана под самые типичные ошибки руки и глаза.

Скромный, но незаменимый

Алгоритм Луна не криптография: он не мешает мошеннику сочинить «правильный» номер, ведь правило открыто. Его задача — отсеивать честные опечатки на лету, не дёргая платёжные системы зря. Эта крошечная арифметическая проверка незаметно работает в каждой онлайн-оплате, экономя время и нервы — наглядный пример того, как чуть-чуть математики делает повседневные технологии надёжнее.