Генерация и валидация чисел по алгоритму Луна

[GospodinKolhoznik]

Алгоритм настолько простой, что даже не знаю, что проще, импортировать зависимость или написать нужную функцию самому.

[GospodinKolhoznik]

В Хаслеле, например, функцию можно реализовать вот так:

isValid :: String -> Bool
isValid = (== 0) . (`mod` 10) . sum . zipWith ($) (cycle [id, \x -> if x < 5 then x*2 else x*2 - 9]) . digits
  where 
    digits = reverse . map (\c -> read [c] )

[AnthonyMikh]

\x -> if x < 5 then x*2 else x*2 - 9

Да проще безусловно брать остаток от деления на 9:

\x -> (x * 2) `mod` 9

[borovichok13]

Алгоритм-то, простой, а вот программисты кривопишущие.

1. В номере карты может быть от 14 до 19 цифр. Ряд поддержки шлюзов, считал, что я не умею считать до 16, время исправления ошибки от недели до нескольких месяцев.

2. Карта МИР может иметь от 16 до 19 цифр. ( у меня с 16 и 19 цифрами).

3. Генератор номера карты может его сгенерить валидным и по 16й и 19й цифрам - одновременно ( у меня такая была). Последствия были таковыми: платёжный шлюз зелёного банка считал, что раз валидна 16я цифра, то нечего платильщику вводить ещё дополнительные цифры. Не сразу, а случайно узнал про алгоритм Луны. Поддержка работает только в рамках стандартного алгоритма - чтобы передать нужную информацию - это ещё тот квест (поставил поддержке единицу, и адекватный сотрудник позвонил на следующий день). Вроде бы исправили через несколько месяцев.

[Helldar]

В ходе работы над проектом выяснил, что:

• AmericanExpress имеет длину в 15 или 16 символов

• HiperCard - 13, 16 или 19 символов

• JCB и UnionPay - от 16 до 19

• VISA - 13 или 16

• VISA Electron - 16 или 17

И самый лютый тип карты из всех - это Maestro - количество символов в её длине может быть от 12 до 19 включительно.

Не исключая криворукости тех, кто это придумал, такой выбор обусловлен, в том числе, наличием других платёжных систем, когда конечный номер карты должен быть уникальным среди всех банковских систем любой страны, по сути. Вот и придумывают изменение длины.

"алгоритм Луны" - не Луны, а Луна. Алгоритм разработал Ханс Лун.

[mentin]

все нечётные цифры

Я бы написал "все цифры на нечётных позициях". А то хоть и понятно что имелось в виду, "нечётные цифры" имеет другое значение.

[Helldar]

Было рассмотрено несколько вариантов этого предложения и каждый раз оно воспринималось двояко. Ваше выглядит лучше. Обновил статью, спасибо!

[borovichok13]

А проверка валидности номера карточки из 19 цифр проверяется ли он, что может быть одновременно валидным и для 16 и 19 цифр? Или других комбинаций?

[Helldar]

Одновременно нет. Сам алгоритм рассчитывает все цифры, а предложенный пакет отдельно проверяет длину строки: https://github.com/TheDragonCode/card-number/blob/main/src/Cards/Card.php#L20-L32

[Didimus]

Начиная отсечёт слева, с нулевой позиции?

[Helldar]

Можно, но это больше действий.

Например:

$number = 18;

$values = str_split((string) $number, 1);

return array_sum($values);

Или:

return $number - 9;

[AlexeyK77]

Интересно узнать даже не за имеено этот алгоритм, а мат. аппарат, который лег в его основу.

Например, если числа будут из другой системы счисления, или может даже это будет просто текст, так какой должен быть алгоритм?

[Helldar]

Так как алгоритм использует, по сути, простейшую математику, можно предположить что в любой системе счисления его будет возможно применить. Разница будет лишь во внешнем виде функции-обработчика.

Что касается текста, то в данном конкретном случае перед обработкой строка очищается от всех символов кроме чисел, а если нужно будет проверять именно буквенную строку, например, "foo-bar-baz", то я бы поступил следующим образом: получил бы для каждой буквы её порядковый номер в алфавите. Если номер больше 9, отнимаем 9 для получения единого числа. Для полученного числа рассчитываем контрольную цифру и на выходе будет готовая строка.

Например:

f  o  o  b a r  b a z
6  15 15 2 1 18 2 1 26
6  6  6  2 1 9  2 1 8  0 // добавляем для определения контрольной цифры
↓     ↓    ↓    ↓   ↓
12 6  12 2 2 9  4 1 16 0
↓     ↓             ↓
3 +6 +6 +2+2+9 +4+1+7 +0 = 40

Получаем контрольную цифру "0" так как полученная сумма делится на 10 без остатка. С учётом того, что цифра может быть от 0 до 9 включительно, в качестве "нуля" можно использовать 10-й символ алфавита - "j".

Таким образом, мы получим верную с точки зрения алгоритма Луна строку foo-bar-baz-j.

[AlexeyK77]

ну, это только предположение, интереснее формальное доказательство, в этом и ыл мой вопрос.

Согласитесь, что то, что алгоритм кажется простым, не делает его тривиальным. Додуматься до такой числовой манипуляции просто так нельзя, за ней стоит определенный мат. аппарат. Вот это мне и было интересно.
Но навреное уже и сам поищу, т.к. не в первый раз уже эта тема вызывает любопытство.

[Helldar]

Статья больше рассчитана на разработчиков, для которых технический язык - родной. Мы же на Хабре, в конце концов. И первое предложение взято из Википедии и чуть упрощено. Оригинал выглядит следующим образом:

Алгоритм Лу́на (англ. Luhn algorithm) — алгоритм вычисления контрольной цифры номера пластиковой карты в соответствии со стандартом ISO/IEC 7812. Не является криптографическим средством, а предназначен в первую очередь для выявления ошибок, вызванных непреднамеренным искажением данных (например, при ручном вводе номера карты, при приёме данных о номере социального страхования по телефону). Позволяет лишь с некоторой степенью достоверности судить об отсутствии ошибок в блоке цифр, но не даёт возможности нахождения и исправления обнаруженной неточности.

https://ru.wikipedia.org/wiki/Алгоритм_Луна

Вдобавок, статья рассчитана не на объяснение истории появление алгоритма, а на его практическое использование с приведёнными примерами расчёта, а также описанием готового пакетного решения на языке PHP для упрощения генерации и валидации чисел.

К тому же, совсем необязательно при чтении поста знать о стандарте ISO/IEC 7812. Эта информация скорее не несёт особого смысла, а указано лишь в качестве связанности алгоритма Луна с ним. Для тех кому интересно что за стандарт, легко могут выделить строчку и загуглить его описание. А те, кому это не интересно, просто пропустят этот участок текста.

[Helldar]

Как скажете.

[Hungryee]

Не обращайте внимания, очевидно, что пан Helldar мало того, что полный профан в написании статей и пытается оправдаться «техническим языком», хотя написал чушь; так еще и обиженка на весь мир, раз за подобные комментарии вам минусует

Статья написана преотвратно, в тексте черт ногу сломит от обилия двояко трактуемых выражений, очень жаль, что боты двигают это вверх

[Didimus]

А как устроено определение платёжной системы? Там же бины могут перераспределяться

[Helldar]

В случае банковских карт платёжные системы применяют формирование номеров карт в соответствии со стандартом ISO/IEC 7812. Это один из международных стандартов, описывающих параметры идентификационных карт и применение таких карт для международного, межотраслевого и/или внутриотраслевого взаимообмена.

Сам стандарт можно прочитать здесь. Он небольшой, всего 12 листов неполного текста.

Формирование номеров по стандарту следующее:

Всегда первые 6 цифр номера - это идентификационный номер эмитента, далее от 4 до 12 цифр - номер лицевого счёта. Последняя цифра - контрольная согласно алгоритму Луна.

Также в номерах банков первая цифра означает тип платёжной системы. Например, 4 - VISA, 5 - MasterCard, 2 - МИР. Но согласно ГОСТ ISO/IEC 7812-1—2014, первая цифра должна означать область деятельности:

1. авиалинии;

2. авиалинии и другие, возможные в будущем, области деятельности;

3. путешествия и развлечения и банковское дело/финансовые услуги;

4. банковское дело/финансовые услуги;

5. банковское дело/финансовые услуги;

6. торговля и банковское дело/финансовые услуги;

7. нефтяная промышленность и другие, возможные в будущем, области деятельности;

8. здравоохранение, телекоммуникации и другие, возможные в будущем, области деятельности;

9. для присвоения национальными органами по стандартизации.

На деле же получаем что банки как бы договариваются друг с другом - авиалинии у себя, а то и не договариваются вовсе, т.к. у каждого своя стойка регистрации и т.д.

Кроме этого, Вы можете заглянуть в эту папку репозитория и посмотреть какие регулярки применяются для определения принадлежности номера той или иной платёжной системе.

[Didimus]

Еще 10-15 лет назад карт МИР не было. А алгоритм был. Потому его тогдашние реализации устарели. Я к чему, алгоритм Луна не относится к определению эмитента карты..

[Helldar]

Немного не так. Устарел стандарт, обновлённый в 2014-м году, судя по его полному названию ISO/IEC 7812-1—2014.

Алгоритм Луна не имеет отношения к определению эмитентов. Он проверяет правильность ввода цифр, не более.

Принадлежность номера банковской карты осуществляется на стороне банков и этот механизм не вписывается в идею этой статьи, т.к. совсем из другой области, никак даже близко не связанной с алгоритмом Луна.

[AlexeyK77]

У алгоритма Луна есть проблема - он не ловит искажение, если идет перестановка цифр 90<->09

[Helldar]

Да, коллизии бывают, особенно там где участвует ноль, но, в целом, справляется.

Например, числа "12901542" и "12091542" валидны, а вот "12911541" валидно, а "12191541" - нет.

[Evg3108]

Недавно читала статью в Википедии, как раз ту, что кинул тут один из товарищей ниже)

Так вот, там в описании алгоритма упоминается 2 варианта: когда в последовательности нечетное количество цифр (и тогда на 2 умножаются цифры на нечётных позициях) и когда их количество чётное (тогда умножаются цифры на четных). У Вас такой момент не освещен. Не могли бы пояснить, почему, пожалуйста?

[Helldar]

По сути, разницы в количестве проверяемых цифр нет. На Вики описано два подхода.

Первый назвали "оригинальным" и в нём действительно есть разница как считать чтобы случайно не захватить в расчёт контрольную цифру. Здесь стоит учесть, что в подсчёте количества символов не нужно учитывать контрольную цифру. Например, число 4567 содержит нечётное количество символов - 3 (456), а 7 - это контрольная цифра

Второй - "упрощённый". По сути, это самый рабочий алгоритм, т.к. в его применении не нужно вычислять количество цифр, а просто идём справа налево выполняя действия над каждой чётной позицией.

Сухой пример расчётов, допустим, на числах 123456 и 1234567:

"Оригинальный" алгоритм:

123456 - количество цифр нечётное, значит, начинаем с первой:
↑ ↑ ↑

1234567 - количество цифр чётное, значит, начинаем со второй:
 ↑ ↑ ↑

"Упрощённый" алгоритм предлагает двигаться справа налево и выполнять действия над каждой второй цифрой:

123456 - в случае нечётного количества
↑ ↑ ↑

1234567 - в случае чётного
 ↑ ↑ ↑

То есть, на выходе мы получим абсолютно такую же картину расчёта за тем исключением, что теперь совсем не нужно вычислять количество символов, определяя его чётность, а просто справа налево берём каждую вторую позицию и вперёд.

[Helldar]

На примере кода, оригинальный будет выглядеть так (сам код не запускал, но должен работать):

function isCorrect(string $number): bool
{
    $sum = 0;

    $length = strlen($number);

    $isEven = ($length - 1) % 10 === 0;

    for ($i = 0; $i < $length; $i++) {
        $digit = (int) $number[$i];

        if ($isEven && $i % 2 !== 0) {
            $digit *= 2;
        } elseif (! $isEven && $i % 2 === 0) {
            $digit *= 2;
        }

        $sum += $digit < 10 ? $digit : $digit - 9;
    }

    return $sum % 10 === 0;
}

И альтернативный способ:

function isCorrect(string $number): bool
{
    $sum = 0;

    $length = strlen($number) - 1;

    for ($i = $length; $i >= 0; --$i) {
        $digit = (int) $number[$i];

        if (($length - $i) % 2) {
            $digit *= 2;
        }

        $sum += ($digit <= 9 ? $digit : $digit - 9);
    }

    return $sum % 10 === 0;
}

[JosefDzeranov]

"далее прибавить к полученному значению сумму всех нечётных цифр"

Вы имели в виду нечетные позиции. Это совсем другое. Поправьте пожалуйста