Формула луна для расчета номера карты

Алгоритм Луна — 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 . В функции эта строка проходит естественно слева направо, то есть наоборот, как в определении алгоритма. Однако, изначально определив, является ли длина строки четной или нечетной, все еще можно удвоить цифры в правильных позициях.

Источник

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

Лун алгоритм, также известная как алгоритм модуль 10 или по модулю 10, простая формула , контрольной суммы используется для проверки различных идентификационных номеров, таких как номера кредитных карт, номер IMEI, канадское социального страхование числа. Формула LUHN была создана в конце 1960-х годов группой математиков. Вскоре после этого, компании-эмитенты кредитных карт приняли его. Поскольку алгоритм находится в свободном доступе, он может использоваться любым. Большинство кредитных карт и многие правительственные идентификационные номера используют алгоритм в качестве простого метода отличия действительных номеров от опечаток или неправильных номеров. Он был разработан для защиты от случайных ошибок, а не от злонамеренных атак.

Давайте разберем алгоритм на примере:
Рассмотрим пример номера счета « 79927398713 «.
Шаг 1 — начиная с крайней правой цифры, удвойте значение каждой второй цифры,

Шаг 2 — Если при удвоении числа получается двухзначное число, т.е. больше 9 (например, 6 × 2 = 12), добавьте цифры продукта (например, 12: 1 + 2 = 3, 15: 1 + 5 = 6), чтобы получить однозначное число.

Шаг 3 — Теперь возьмите сумму всех цифр.

Шаг 4 — Если сумма по модулю 10 равна 0 (если сумма заканчивается на нуле), то число действует в соответствии с формулой Луна; иначе это не действует.

Поскольку сумма равна 70, что кратно 10, номер счета, возможно, действителен.

Идея проста, мы переходим от конца. Для каждой второй цифры мы удваиваем ее перед добавлением. Мы добавляем две цифры числа, полученного после удвоения.

// Программа CPP для реализации алгоритма Луна
#include

using namespace std;

// Возвращает true, если данный номер карты действителен

bool checkLuhn( const string& cardNo)

int nDigits = cardNo.length();

int nSum = 0, isSecond = false ;

for ( int i = nDigits — 1; i >= 0; i—) <

int d = cardNo[i] — ‘0’ ;

if (isSecond == true )

// Добавляем две цифры для обработки

// случаи, которые делают две цифры после

return (nSum % 10 == 0);

string cardNo = «79927398713» ;

printf ( «This is a valid card» );

printf ( «This is not a valid card» );

// Java-программа для реализации
// алгоритм Луна

// Возвращает true если дано
// номер карты действителен

static boolean checkLuhn(String cardNo)

int nDigits = cardNo.length();

boolean isSecond = false ;

for ( int i = nDigits — 1 ; i >= 0 ; i—)

int d = cardNo.charAt(i) — ‘0’ ;

if (isSecond == true )

// Добавляем две цифры для обработки

// случаи, которые делают две цифры

return (nSum % 10 == 0 );

static public void main (String[] args)

String cardNo = «79927398713» ;

System.out.println( «This is a valid card» );

System.out.println( «This is not a valid card» );

// Этот код предоставлен vt_m.

// C # программа для реализации
// алгоритм Луна

// Возвращает true если дано
// номер карты действителен

static bool checkLuhn(String cardNo)

int nDigits = cardNo.Length;

bool isSecond = false ;

for ( int i = nDigits — 1; i >= 0; i—)

int d = cardNo[i] — ‘0’ ;

if (isSecond == true )

// Добавляем две цифры для обработки

// случаи, которые делают две цифры

return (nSum % 10 == 0);

static public void Main()

String cardNo = «79927398713» ;

Console.WriteLine( «This is a valid card» );

Console.WriteLine( «This is not a valid card» );

// Этот код предоставлен vt_m.

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

Источник:
https://en.wikipedia.org/wiki/Luhn_algorithm

Эта статья предоставлена Вишалом Кумаром Гуптой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Источник