Контрольная сумма по алгоритму луна

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

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

Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/2464/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).

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

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

Источник

Алгоритм Луна — 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-карт.

Источник

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

Лун алгоритм или формула Лун , также известная как « Modulo 10» или «10» по модулю алгоритма и двойной надстройке двойной метод, простой метод для вычисления контрольной суммы . Он был разработан в 1950-х годах немецко-американским ученым-компьютерщиком Гансом Петером Луном и сейчас находится в общественном достоянии и очень широко распространен. Среди прочего, алгоритм Лун используется для проверки номеров кредитных карт и канадские номера социального страхования , кодов ISIN и семизначный номер счета от Deutsche Bank и Commerzbank , а также многих сберегательных банков . Он также используется для номеров локомотивов и железнодорожных вагонов в соответствии со схемой маркировки UIC , как это было в случае с последовательной схемой Bundesbahn с 1968 года .

Алгоритм Луна распознает каждую ошибку в отдельных цифрах, а также, в большинстве случаев, перестановки соседних цифр.

Оглавление

Неформальное объяснение

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

1. Пройдите цифру за цифрой справа налево и сформируйте сумму цифр, но: Удвойте каждую вторую цифру, и если результат больше 9, вычтите 9
2. Если в итоговой сумме последней цифрой является 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.

Источник