Алгоритм Луна
Алгоритм Лу́на (англ. Luhn algorithm ) — алгоритм вычисления контрольной цифры номера пластиковых карт в соответствии со стандартом ISO/IEC 7812. Не является криптографическим средством, предназначение алгоритма в первую очередь — выявление ошибок, вызванных непреднамеренным искажением данных (например, при ручном вводе номера карты, при приёме данных о номере социального страхования по телефону). Позволяет лишь с некоторой степенью достоверности судить об отсутствии ошибок в блоке цифр, но не даёт возможности локализации и коррекции обнаруженной неточности.
Алгоритм разработан сотрудником фирмы IBM Гансом Питером Луном, описан в США в 1954 году, патент получен в 1960 году.
Наиболее распространённые применения для подсчёта контрольной цифры:
- Номера всех банковских карт
- Номера некоторых дисконтных карт
- Коды социального страхования
- IMEI-коды.
В настоящее время содержание алгоритма является публичным достоянием.
Содержание
Достоинства и недостатки
В силу простоты реализации, алгоритм отнимает минимум вычислительных мощностей; в ряде случаев при наличии навыка расчёт может быть произведён «в уме». В то же время, алгоритм Луна позволяет только выявить ошибки в блоках данных, и то не все. Искажение одной цифры — обнаруживается. Обнаруживаются практически все парные перестановки подряд идущих цифр (за исключением 09 ↔ 90). Не могут быть обнаружены некоторые искажения двух подряд идущих цифр, а именно 22 ↔ 55, 33 ↔ 66 и 44 ↔ 77. Алгоритм не даёт информации о месте и характере возникшей ошибки.
Алгоритм может применяться для последовательностей цифр любой длины, однако при этом следует иметь в виду, что при достаточно длинных числах вероятно появление одновременно нескольких искажений данных; некоторые из таких ошибок могут привести к ошибочному выводу, что контрольное число, вычисленное по алгоритму Луна, подтверждает неизменность данных.
Алгоритм проверки контрольной цифры
Упрощённый алгоритм
1. Начиная с первой цифры слева через 1 (то есть 1, 3, 5, 7, 9, …) делается проверка: если 2·x > 9, то из произведения вычитается 9, если 2·x Оригинальный алгоритм, описанный разработчиком
1. Цифры проверяемой последовательности нумеруются справа налево.
2. Цифры, оказавшиеся на нечётных местах, остаются без изменений.
3. Цифры, стоящие на чётных местах, умножаются на 2.
4. Если в результате такого умножения возникает число больше 9, оно заменяется суммой цифр получившегося произведения — однозначным числом, т. е. цифрой.
5. Все полученные в результате преобразования цифры складываются. Если сумма кратна 10, то исходные данные верны.
Аналоги
Источники информации
- U.S. Patent 2 950 048Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.
Ссылки
Wikimedia Foundation . 2010 .
Смотреть что такое «Алгоритм Луна» в других словарях:
Алгоритм Верхоффа — (Verhoeff) алгоритм расчёта контрольной цифры для обнаружения ошибок при ручном вводе длинных цифровых последовательностей. Впервые опубликован в 1969 г. голландским математиком Якобом Верхоффом. Алгоритм позволяет выявить большее число… … Википедия
Контрольное число — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
Контрольная сумма — Контрольная сумма некоторое значение, рассчитанное по набору данных путём применения определённого алгоритма и используемое для проверки целостности данных при их передаче или хранении. Также контрольные суммы могут использоваться для… … Википедия
CVV2 — на карте VISA CVV2 (англ. Card Verification Value 2) трёхзначный или четырёхзначный код проверки подлинности карты платёжной системы Visa. Другие платёжные системы имеют сходные технологии, к примеру аналогичный защитный код для карт… … Википедия
Дни недели — Названия дней недели с римского периода были, с одной стороны, связаны с названиями семи планет классической астрономии, а с другой стороны, первым днём недели считалось воскресенье. Обе эти системы были приняты во многих языках, за некоторыми… … Википедия
Контрольная цифра — Контрольное число, контрольная цифра разновидность контрольной суммы, добавляется (обычно в конец) длинных номеров с целью первичной проверки их правильности. Применяется с целью уменьшения вероятности ошибки при обработке таких номеров: машинном … Википедия
Список русскоязычных японистов — составлен на основе справочника С. Д. Милибанд «Востоковеды России» (в 2 т. М.: Вост. лит., 2008) В список, как правило, не включены переводчики японской литературы (кроме случаев, когда перевод сопровождается комментарием и имеет… … Википедия
Логлан — Самоназвание: La Logla Создан: Джеймс Кук Браун Регулирующая организация: Институт логлана (англ. The Loglan Institute)[1] … Википедия
Источник
Алгоритм Луна
Лун алгоритм или формула Лун , также известная как « Modulo 10» или «10» по модулю алгоритма и двойной надстройке двойной метод, простой метод для вычисления контрольной суммы . Он был разработан в 1950-х годах немецко-американским ученым-компьютерщиком Гансом Петером Луном и сейчас находится в общественном достоянии и очень широко распространен. Среди прочего, алгоритм Лун используется для проверки номеров кредитных карт и канадские номера социального страхования , кодов ISIN и семизначный номер счета от Deutsche Bank и Commerzbank , а также многих сберегательных банков . Он также используется для номеров локомотивов и железнодорожных вагонов в соответствии со схемой маркировки UIC , как это было в случае с последовательной схемой Bundesbahn с 1968 года .
Алгоритм Луна распознает каждую ошибку в отдельных цифрах, а также, в большинстве случаев, перестановки соседних цифр.
Оглавление
Неформальное объяснение
Алгоритм Луна генерирует контрольную цифру , которая обычно добавляется в конец неполного идентификационного номера. Это дает полное число. Это считается действительным, если он проходит следующий алгоритм проверки:
- Пройдите цифру за цифрой справа налево и сформируйте сумму цифр, но: Удвойте каждую вторую цифру, и если результат больше 9, вычтите 9
- Если в итоговой сумме последней цифрой является 0, распознайте это число как действительное, а не иначе.
Например, для проверки числа 18937 цифры вводятся справа налево, т.е. начиная с 7, и складываются. Каждая вторая цифра удваивается, то есть в этом примере это 3 и 8. Поскольку удвоение 8 приводит к значению больше 9, из него вычитается 9, так что 16-9 = 7.
Таким образом, сумма рассчитывается как 7 + (2 × 3) + 9 + (2 × 8 — 9) + 1 = 7 + 6 + 9 + 7 + 1 = 30. Поскольку 30 заканчивается на 0, число действительно.
Технически вычисляется своего рода перекрестная сумма числа с особым подходом к каждой второй цифре. Результат уменьшается по модулю 10; Это означает, что он не зависит от самого результата, а только от остатка, который получается при делении на 10 как целое число. Этот остаток равен последней цифре результата.
Если этот остаток равен 0, что означает, что результат делится на 10, число считается действительным, в противном случае — нет.
Алгоритм Луна распознает неправильный ввод числа при вводе числа. Это изменяет общую сумму на величину от 1 до 9 и, следовательно, больше не делится на 10. Если ввести 4 вместо 1 в приведенном выше примере, результат будет 33 и, следовательно, не делится на 10. Если ввести 6 вместо 8, результат будет 26 и, следовательно, не делится на 10.
Единичный неправильный ввод числа также будет распознан при обычном формировании контрольной суммы, но не при одной из часто встречающихся « ротаций чисел », то есть перестановки двух последовательных чисел. Это не повлияет на обычную контрольную сумму.
Алгоритм Луна распознает такой ротатор чисел, удваивая другую цифру, чем раньше, и изменяя контрольную сумму. Например, число 190 является действительным (контрольная сумма Luhn 10), а 910 — нет (контрольная сумма Luhn 11), т.е. ЧАС. число, повернутое с 19 на 91, распознается. Единственное исключение — это повернутые числа цифр 0 и 9, так как их контрольные суммы одинаковы с удвоением и без него. Например, 190 и 109 действительны (контрольная сумма Луна 10); ЧАС. число, повернутое с 90 на 09, не распознается.
Перестановки цифр, позиции которых различаются на четную величину, не распознаются — например, если меняются местами 3-я и 5-я цифры или 2-я и 6-я цифры. Точно так же он может быть не распознан, если две или более цифр введены неправильно.
Примеры реализации
В следующих реализациях алгоритма число передается number в функцию как последовательность символов, то есть как строка checkLuhn . В функции эта строка проходит естественно слева направо, то есть наоборот, как в определении алгоритма. Однако, изначально определив, является ли длина строки четной или нечетной, все еще можно удвоить цифры в правильных позициях.
Источник
Алгоритм Луна
Алгоритм Луна (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.
Источник
Алгоритм Луна для проверки номеров кредитных карт и т. Д.
Вызов
Напишите самую короткую программу или функцию для расчета алгоритма Луна для проверки номеров (кредитных карт).
Алгоритм Луна объяснил
От RosettaCode этот алгоритм для целей этой задачи указан как таковой, с примером ввода 49927398716 :
Правила IO
Ввод : строка или число (на ваш выбор) в выбранном вами формате ввода / вывода.
Вывод : истинное или ложное значение , соответственно, указывающее, является ли ввод действительным в соответствии с тестом выше.
Примечания / Советы
Старайтесь не оставлять случайно свои номера кредитных карт или счетов, если вы используете их для проверки 🙂
Если ввод неверен и его невозможно обработать с помощью указанного алгоритма (т. Е. Слишком короток для работы), вы можете делать все, что захотите, в том числе взорвать мой компьютер.
Однако предыдущий пункт не означает, что ваш язык может делать все, что захочет, с числами, которые слишком велики для него. Если ваш язык не способен обрабатывать контрольные примеры, подумайте о том, чтобы взять строку в качестве входных данных.
Примеры
Следующие примеры были проверены с помощью этого скрипта Python ; если вы думаете, что кто-то не прав или у вас есть вопрос, просто пинг @cat.
** в соответствии с реализацией Python, но вы можете сделать что-нибудь, потому что они слишком короткие, чтобы соответствовать строгой приверженности спецификации.
Если что-либо из вышеперечисленного лишает законной силы существующие ответы (хотя я считаю, что это не должно быть возможно), то эти ответы все еще действительны. Тем не менее, новые ответы, чтобы быть действительными, должны соответствовать спецификации выше.
Leaderboard
Golfscript — 24 символа
- -1% переворачивает строку
- < начинается блок (который мы используем в качестве цикла). Каждый символ в строках вставляется в качестве значения ascii.
- 2+ добавляет 2. (значение ASCII цифры 48 + n, поэтому у нас сейчас 50 + n и последняя цифра n)
- 0!:0 инвертирует значение 0 и сохраняет его (все является переменной), поэтому мы имеем 1 на первой итерации, 0 на второй и т. д.
- )* добавляет к этому значению единицу и умножает ее, поэтому мы умножаем на 2, затем на 1, затем на 2 и т. д.
- 109% является остатком по модулю 109. Это влияет только на значения 5-9, которые были удвоены, и уменьшает их до правильного значения.
- + добавляет это значение к текущей сумме
- >* заканчивает блок и выполняет операцию «сгиба». Сначала нажимается первый символ (поскольку мы поменяли местами, это контрольная цифра). Затем чередуйте нажатие и выполнение блока. Таким образом, мы используем значение ascii первого символа в качестве начального значения для текущей суммы.
- 10% берет остаток по модулю 10.
- 8= вернет 1, если значение равно 8. Мы используем это, потому что мы не нормализовали первый нажатый символ (контрольная цифра).
Можно подумать, что мы могли бы использовать 8- вместо того, 2+ чтобы сохранить символ, изменив 109% на 89% , за исключением того, что нам нужно было бы добавить пробел, чтобы — вычитание было (вместо -0 ).
GolfScript, 44 символа
Выбранный комментарий
Интересно, что первые два пункта ниже демонстрируют три совершенно разных использования % оператора: выбор массива, отображение и мод. Большинство операторов GolfScript являются «контекстно-зависимыми», что дает им чрезвычайно различное поведение в зависимости от типов аргументов.
- -1% переворачивает строку Это важно, так как пары цифр отсчитываются справа.
- <16%>% преобразует все цифры ASCII в числа, модифицируя их 16.
- 2/ разбивает массив на группы по 2.
- 1, это дешевый способ сделать [0] .
- \+ эффективно добавляет 0 к массиву цифр. Это происходит путем замены, а затем конкатенации.
0 готовится к следующей фолде. Вместо того, чтобы принимать явное начальное значение, сгиб GolfScript использует первый элемент в массиве в качестве начального значения.
Теперь давайте посмотрим на фактическую функцию сгиба. Эта функция принимает два аргумента: сложенное значение и текущий элемент в массиве (который в этом случае будет массивом из 2 или (необычно) 1 из-за 2/ более раннего). Давайте предположим, что аргументы 1 [2 3] .
- (\. разбивает крайний левый элемент массива, перемещает оставшийся массив вперед, а затем копирует его. Стек теперь выглядит следующим образом : 1 2 [3] [3] .
- В if проверяет , является ли массив пуст (что имеет место для последней группы , когда дело с нечетным размером номера счета). Если это так, то никакой специальной обработки не происходит (просто выскочить из пустого массива).
- Для четной группы:
- 0= захватывает первый (в данном случае, единственный) элемент массива. 1 2 3
- 2* удваивает число 1 2 6
- .9>9*- вычитает 9 из числа, если оно больше 9. Реализовано так: скопируйте число, сравните с 9, умножьте результат (или 0 или 1) на 9, затем вычтите. 1 2 6
- + наконец добавляет это к первому номеру. 1 8
- + (после if ) добавляет результат if к исходному значению, что приводит к новому сложенному значению.
После завершения сворачивания мы просто модифицируем 10 ( 10% ) и отменяем результат ( ! ), так что мы возвращаем 1, если сумма кратна 10.
Источник