Проверка номера карты алгоритмом луна

Алгоритм Луна

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

Алгоритм определяет ошибки ввода одной неправильной цифры, а также практически все парные перестановки подряд идущих цифр (за исключением 09 ↔ 90).

Онлайн калькулятор выдает последнюю цифру контрольной суммы, полученной алгоритмом Луна из заданной последовательности. Также вычисляется проверочная цифра, которая может быть добавлена к исходной последовательности, чтобы получить корректную последовательность (т.е. последовательность, контрольная сумма которой оканчивается на 0).

Алгоритм проверки контрольной цифры

1. Цифры проверяемой последовательности нумеруются справа налево.

2. Цифры, оказавшиеся на нечётных местах, остаются без изменений.

3. Цифры, стоящие на чётных местах, умножаются на 2.

4. Если 2·x > 9, то из произведения вычитается 9, иначе произведение 2·x оставляем без изменения, где x — текущая цифра.

5. Затем все числа, полученные на предыдущем этапе, складываются.

6. Полученная сумма должна быть кратна 10 (то есть равна 40, 50, 60, 70, …). В примере выше исходная последовательность некорректна.

В примере: последняя цифра — контрольная. Для того, чтобы номер был верен в соответствии с алгоритмом Луна, контрольная цифра должна быть равна 7.

Алгоритм нахождения следующей проверочной цифры

Чтобы найти проверочную цифру, которая может быть добавлена к исходной последовательности, чтобы получить корректную последовательность (т.е. последовательность, контрольная сумма которой оканчивается на 0) необходимо добавить 0 к исходной последовательности и вычислить контрольную сумму полученной последовательности алгоритмом Луна. Если полученная контрольная сумма оканчивается на 0, то следующая проверочная цифра это и есть 0, в противном случае проверочная цифра определяется путем вычитания последней цифры полученной контрольной суммы из 10.

Источник

Алгоритм Луна — Luhn algorithm

Лун алгоритм или формула Лун , также известный как « модуль 10» или « по модулю 10» алгоритм , названный в честь его создателя, IBM ученый Ханс Петер Лун , это простая контрольная формула используется для проверки различных идентификационных номеров, таких как кредит номера карт , номер IMEI , Национальный Provider номер идентификаторы в США, канадское социальное страхование числа , израильские идентификационные номера, южноафриканские идентификационные номера, греческие номера социального страхования (ΑΜΚΑ), а также опрос кода , появляющаяся на Макдональдсе , Taco Bell и тракторное питание Квитанции Ко . Он описан в патенте США № 2,950,048 , поданном 6 января 1954 г. и выданном 23 августа 1960 г.

Алгоритм является общественным достоянием и широко используется сегодня. Это указано в ISO / IEC 7812-1 . Он не предназначен для использования в качестве криптографически безопасной хеш-функции ; он был разработан для защиты от случайных ошибок, а не от злонамеренных атак. Большинство кредитных карт и многие государственные идентификационные номера используют алгоритм в качестве простого метода отличия действительных номеров от набранных с ошибками или иным образом неправильных номеров.

СОДЕРЖАНИЕ

Описание

Формула сравнивает число с включенной контрольной цифрой , которая обычно добавляется к частичному номеру счета для генерации полного номера счета. Этот номер должен пройти следующий тест:

1. Начиная с самой правой цифры (исключая контрольную цифру) и двигаясь влево, удвойте значение каждой второй цифры. Контрольная цифра не удваивается и не включается в этот расчет; первая удвоенная цифра — это цифра, расположенная сразу слева от контрольной цифры. Если результат этой операции удвоения больше 9 (например, 8 × 2 = 16), тогда сложите цифры результата (например, 16: 1 + 6 = 7, 18: 1 + 8 = 9) или, что то же самое, , вычтите 9 из результата (например, 16: 16 — 9 = 7, 18: 18 — 9 = 9).
2. Возьмите сумму всех цифр (включая контрольную).
3. Если сумма по модулю 10 равна 0 (если сумма заканчивается нулем), то число действительно согласно формуле Луна; в противном случае это недействительно.

Пример вычисления контрольной цифры

Предположим, что для номера счета «7992739871» будет добавлена ​​контрольная цифра, которая будет иметь форму 7992739871x:

Сумма всех цифр в третьей строке, сумма цифр суммы, равна 67.

Контрольная цифра (x) получается путем вычисления суммы цифр суммы, а затем вычисления 9-кратного значения по модулю 10 (в форме уравнения ((67 × 9) по модулю 10)). В виде алгоритма:

1. Вычислите сумму цифр суммы (67).
2. Умножьте на 9 (603).
3. 603 mod 10 — это контрольная цифра 3. Таким образом, x = 3 .

(Альтернативный метод) Контрольная цифра (x) получается путем вычисления суммы других цифр (третья строка), а затем вычитания цифры единиц из 10 (67 => цифра единиц 7; 10-7 = контрольная цифра 3; в форме уравнения , 10 — (67 мод 10)). В виде алгоритма:

1. Вычислите сумму цифр суммы (67).
2. Возьмите цифру единиц (7).
3. Вычтите цифру единиц из 10.
4. Результат (3) — это контрольная цифра. Если сумма цифр оканчивается на 0, тогда 0 является контрольной цифрой.

Это делает полный номер счета 79927398713.

Пример проверки контрольной цифры

Каждый из номеров 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 можно проверить следующим образом.

1. Удваивайте каждую вторую цифру, начиная с самого правого: (1 × 2) = 2, (8 × 2) = 16, (3 × 2) = 6, (2 × 2) = 4, (9 × 2) = 18
2. Суммируйте все отдельные цифры (цифры в скобках — это произведения из шага 1): x (контрольная цифра) + (2) + 7 + (1 + 6) + 9 + (6) + 7 + (4) + 9 + (1 + 8) + 7 = х + 67.
3. Если сумма кратна 10, возможно, номер счета действителен. Обратите внимание, что 3 — единственная допустимая цифра, которая дает сумму (70), кратную 10.
4. Таким образом, все эти номера счетов недействительны, за исключением, возможно, 79927398713, у которого есть правильная контрольная цифра.

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

Сильные и слабые стороны

Алгоритм Луна обнаружит любую ошибку, связанную с одной цифрой, а также почти все перестановки соседних цифр. Однако он не обнаружит транспонирование двузначной последовательности 09 в 90 (или наоборот). Он обнаружит большинство возможных двойных ошибок (он не обнаружит 22 ↔ 55 , 33 ↔ 66 или 44 ↔ 77 ).

Другие, более сложные алгоритмы проверки цифр (например, Verhoeff алгоритм и алгоритм Дамм ) могут обнаружить больше ошибок транскрипции. Лун мод N алгоритм является расширением , которое поддерживает нечисловые строки.

Поскольку алгоритм работает с цифрами справа налево, а нулевые цифры влияют на результат только в том случае, если они вызывают сдвиг позиции, заполнение нулями начала строки чисел не влияет на вычисления. Следовательно, системы, которые дополняют определенное количество цифр (например, путем преобразования 1234 в 0001234), могут выполнять проверку Luhn до или после заполнения и достигать того же результата.

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

Алгоритм появился в патенте США на портативное механическое устройство для вычисления контрольной суммы. Следовательно, требовалось, чтобы это было достаточно просто. Устройство взяло мод 10 сум механическим способом. Эти замены цифры , то есть, результаты двойной и сокращения процедуры, не были получены механическим способом . Скорее, цифры были отмечены на корпусе машины в порядке их перестановки.

Реализация псевдокода

Применение

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

Источник

Алгоритм Луна для проверки номеров кредитных карт и т. Д.

Вызов

Напишите самую короткую программу или функцию для расчета алгоритма Луна для проверки номеров (кредитных карт).

Алгоритм Луна объяснил

От RosettaCode этот алгоритм для целей этой задачи указан как таковой, с примером ввода 49927398716 :

Правила IO

Ввод : строка или число (на ваш выбор) в выбранном вами формате ввода / вывода.

Вывод : истинное или ложное значение , соответственно, указывающее, является ли ввод действительным в соответствии с тестом выше.

Примечания / Советы

Старайтесь не оставлять случайно свои номера кредитных карт или счетов, если вы используете их для проверки 🙂

Если ввод неверен и его невозможно обработать с помощью указанного алгоритма (т. Е. Слишком короток для работы), вы можете делать все, что захотите, в том числе взорвать мой компьютер.

Однако предыдущий пункт не означает, что ваш язык может делать все, что захочет, с числами, которые слишком велики для него. Если ваш язык не способен обрабатывать контрольные примеры, подумайте о том, чтобы взять строку в качестве входных данных.

Примеры

Следующие примеры были проверены с помощью этого скрипта Python ; если вы думаете, что кто-то не прав или у вас есть вопрос, просто пинг @cat.

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

Если что-либо из вышеперечисленного лишает законной силы существующие ответы (хотя я считаю, что это не должно быть возможно), то эти ответы все еще действительны. Тем не менее, новые ответы, чтобы быть действительными, должны соответствовать спецификации выше.

Leaderboard

Golfscript — 24 символа

1. -1% переворачивает строку
2. < начинается блок (который мы используем в качестве цикла). Каждый символ в строках вставляется в качестве значения ascii.
   1. 2+ добавляет 2. (значение ASCII цифры 48 + n, поэтому у нас сейчас 50 + n и последняя цифра n)
   2. 0!:0 инвертирует значение 0 и сохраняет его (все является переменной), поэтому мы имеем 1 на первой итерации, 0 на второй и т. д.
   3. )* добавляет к этому значению единицу и умножает ее, поэтому мы умножаем на 2, затем на 1, затем на 2 и т. д.
   4. 109% является остатком по модулю 109. Это влияет только на значения 5-9, которые были удвоены, и уменьшает их до правильного значения.
   5. + добавляет это значение к текущей сумме
3. >* заканчивает блок и выполняет операцию «сгиба». Сначала нажимается первый символ (поскольку мы поменяли местами, это контрольная цифра). Затем чередуйте нажатие и выполнение блока. Таким образом, мы используем значение ascii первого символа в качестве начального значения для текущей суммы.
4. 10% берет остаток по модулю 10.
5. 8= вернет 1, если значение равно 8. Мы используем это, потому что мы не нормализовали первый нажатый символ (контрольная цифра).

Можно подумать, что мы могли бы использовать 8- вместо того, 2+ чтобы сохранить символ, изменив 109% на 89% , за исключением того, что нам нужно было бы добавить пробел, чтобы — вычитание было (вместо -0 ).

GolfScript, 44 символа

Выбранный комментарий

Интересно, что первые два пункта ниже демонстрируют три совершенно разных использования % оператора: выбор массива, отображение и мод. Большинство операторов GolfScript являются «контекстно-зависимыми», что дает им чрезвычайно различное поведение в зависимости от типов аргументов.

1. -1% переворачивает строку Это важно, так как пары цифр отсчитываются справа.
2. <16%>% преобразует все цифры ASCII в числа, модифицируя их 16.
3. 2/ разбивает массив на группы по 2.
4. 1, это дешевый способ сделать [0] .
5. \+ эффективно добавляет 0 к массиву цифр. Это происходит путем замены, а затем конкатенации.

0 готовится к следующей фолде. Вместо того, чтобы принимать явное начальное значение, сгиб GolfScript использует первый элемент в массиве в качестве начального значения.

Теперь давайте посмотрим на фактическую функцию сгиба. Эта функция принимает два аргумента: сложенное значение и текущий элемент в массиве (который в этом случае будет массивом из 2 или (необычно) 1 из-за 2/ более раннего). Давайте предположим, что аргументы 1 [2 3] .

1. (\. разбивает крайний левый элемент массива, перемещает оставшийся массив вперед, а затем копирует его. Стек теперь выглядит следующим образом : 1 2 [3] [3] .
2. В if проверяет , является ли массив пуст (что имеет место для последней группы , когда дело с нечетным размером номера счета). Если это так, то никакой специальной обработки не происходит (просто выскочить из пустого массива).
3. Для четной группы:
   1. 0= захватывает первый (в данном случае, единственный) элемент массива. 1 2 3
   2. 2* удваивает число 1 2 6
   3. .9>9*- вычитает 9 из числа, если оно больше 9. Реализовано так: скопируйте число, сравните с 9, умножьте результат (или 0 или 1) на 9, затем вычтите. 1 2 6
   4. + наконец добавляет это к первому номеру. 1 8
4. + (после if ) добавляет результат if к исходному значению, что приводит к новому сложенному значению.

После завершения сворачивания мы просто модифицируем 10 ( 10% ) и отменяем результат ( ! ), так что мы возвращаем 1, если сумма кратна 10.

Источник