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


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

Алгоритм разработан сотрудником фирмы IBM Хансом Питером Луном, описан в США в 1954 году, патент получен в 1960 году.

Наиболее распространённые применения для подсчёта контрольной цифры:

  • Номера всех банковских карт
  • Номера некоторых дисконтных карт
  • Коды социального страхования
  • IMEI-коды.
  • Расчёт контрольного знака единого 8-значного номера железнодорожного вагона на РЖД.
  • Расчёт ICCID (англ. integrated circuit card identifier) — уникальный серийный номер SIM-карты.

В настоящее время алгоритм является публичным достоянием.

Достоинства и недостатки

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

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

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

Оригинальный алгоритм, описанный разработчиком

1. Начиная с первой цифры последовательности слева и через одну цифру (то есть позиции 1, 3, 5, 7, 9, …) в случае, если количество цифр в последовательности нечетное (как в этом примере, где оно равно 15, 16 — контрольная), если же количество цифр четное, тогда, начиная со второй цифры последовательности через одну цифру (то есть позиции 2, 4, 6, 8, …), делается проверка: если 2·x > 9, то из произведения вычитается 9, иначе произведение 2·x оставляем без изменения, где x — текущая цифра.

например:

4 5 6 1 2 6 1 2 1 2 3 4 5 4 6 4 8 12 4 2 2 6 10 12 8 3 4 2 2 6 1 3

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

8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+4 = 57

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

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

4 5 6 1 2 6 1 2 1 2 3 4 5 4 6 7 8 12 4 2 2 6 10 12 8 3 4 2 2 6 1 3 8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+7 = 60

Упрощённый алгоритм

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

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

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

4. Если в результате такого умножения возникает число больше 9, оно заменяется суммой цифр получившегося произведения — однозначным числом, то есть цифрой.

5. Все полученные в результате преобразования цифры складываются. Если сумма кратна 10, то исходные данные верны.

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

VBA

Num[1..N] — номер карты, Num[N] — контрольная цифра.

sum = 0 for i = 1 to N-1 do p = Num[N-i] if (i mod 2 <> 0) then p = 2*p if (p > 9) then p = p - 9 end if end if sum = sum + p next i //дополнение до 10 sum = 10 - (sum mod 10) if (sum == 10) then sum = 0 end if Num[N] = sum

Java

import java.util.*; import java.lang.String; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.print("Enter the number: "); String value = scan.next(); int sum1 = 0; int sum2=0; final int nDigits = value.length(); for (int i = nDigits; i> 0; i--){ int digit = Character.getNumericValue(value.charAt(i-1)); int z=digit;int y=digit; if (i % 2 == 0){ z *= 2; if (z > 9) { z -= 9; } sum1 += z; } else sum2 += y; } int sum=sum1+sum2; if (value.length()!=16) sum=1; System.out.println(sum); if (sum%10 == 0){ System.out.println ("Card Valid"); } else { System.out.println("Card not Valid"); } } }

C

#include <string.h> // заголовок объявляющий функцию strlen() int luhn(const char* card_number) // принимаем в аргументы номер карты { int len = strlen(card_number); // узнаем длину номера карты int number = 0; // текущая цифра в цикле (см. ниже) int check_digit = 0; // переменная которая будет хранить проверочную цифру int i; for(i = 0; i < len; i++) // главный цикл, в процессе него вычисляется проверочная цифра { number = card_number[i] - '0'; // переводим цифру из char в int if(i % 2 != 0) // если позиция цифры нечётное, то: { number *= 2; // умножаем цифру на 2 if(number > 9) // согласно алгоритму, ни одно число не должно быть больше 9 { number -= 9; // второй вариант сведения к единичному разряду } } check_digit += number; // прибавляем к check_digit номера согласно алгоритму } return (check_digit * 9) % 10; // возвращаем проверочное число вычисленное согласно алгоритму }

C++

#include <string> int luhn(std::string input) { int number = 0; int check_digit = 0; for(int i = 0; i < input.length(); i++) { number = input[i-1] - '0'; if((i-1) % 2 != 0) { number *= 2; if(number > 9) { number -= 9; } } check_digit += number; } return (check_digit * 9) % 10; }

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

Псевдокод

function checkLuhn(string purportedCC) { int sum := 0 int nDigits := length(purportedCC) int parity := nDigits modulus 2 for i from 0 to nDigits - 1 { int digit := integer(purportedCC[i]) if i modulus 2 = parity digit := digit × 2 if digit > 9 digit := digit - 9 sum := sum + digit } return (sum modulus 10) = 0 }

C

#include <stdbool.h> // для типа bool #include <string.h> // для strlen() bool checkLuhn(const char* card_number) // принимаем в аргументы номер карты { int len = strlen(card_number); // узнаем длину номера карты int number = 0; // текущая цифра в цикле (см. ниже) int sum = 0; // переменная которая будет хранить проверочную сумму цифр for(int i = 0; i < len; i++) // главный цикл, в процессе которого проверяется валидность номера карты { number = card_number[i] - '0'; // переводим цифру из char в int if(i % 2 == 0) // если позиция цифры чётное, то: { number *= 2; // умножаем цифру на 2 if(number > 9) // согласно алгоритму, ни одно число не должно быть больше 9 { number -= 9; // второй вариант сведения к единичному разряду } } sum += number; // прибавляем к sum номера согласно алгоритму } if(sum % 10 == 0) // если проверочная сумма чётно делится на 10, то: { return true; // номер карты введён верно! } else // в любом другом случае: { return false; // при введении номера карты была допущена ошибка } }

C++

#include <string> bool checkLuhn(std::string input) { int len = input.length(); int number = 0; int sum = 0; for(int i = len; i > 0; i--) { number = input[i] - '0'; if(i % 2 == 0) { number *= 2; if(number > 9) { number -= 9; } } sum += number; } return sum % 10 == 0; }

Python

from functools import reduce def luhn(code): # Предварительно рассчитанные результаты умножения на 2 с вычетом 9 для больших цифр # Номер индекса равен числу, над которым проводится операция LOOKUP = (0, 2, 4, 6, 8, 1, 3, 5, 7, 9) code = reduce(str.__add__, filter(str.isdigit, code)) evens = sum(int(i) for i in code[-1::-2]) odds = sum(LOOKUP[int(i)] for i in code[-2::-2]) return ((evens + odds) % 10 == 0) print("Прошел проверку: ", luhn('4561 2612 1234 5467')) print("Не прошел проверку: ", luhn('4561 2612 1234 5464'))

JavaScript

function luhnAlgorithm(value) { value = value.replace(/D/g, ''); var nCheck = 0; var bEven = false; for (var n = value.length - 1; n >= 0; n--) { var nDigit = parseInt(value.charAt(n), 10); if (bEven && (nDigit *= 2) > 9) { nDigit -= 9; } nCheck += nDigit; bEven = !bEven; } return (nCheck % 10) == 0; } // Вариант покороче const Moon_Algorithm = setValue => { let ch = 0; const num = String(setValue).replace(/D/g, ''); const isOdd = num.length % 2 !== 0; if ('' === num) return false; for (let i = 0; i < num.length; i++) { let n = parseInt(num[i], 10); ch += (isOdd | 0) === (i % 2) && 9 < (n *= 2) ? (n - 9) : n; } return 0 === (ch % 10); };

PHP

function luhnAlgorithm($digit) { $number = strrev(preg_replace('/[^d]+/', '', $digit)); $sum = 0; for ($i = 0, $j = strlen($number); $i < $j; $i++) { if (($i % 2) == 0) { $val = $number[$i]; } else { $val = $number[$i] * 2; if ($val > 9) { $val -= 9; } } $sum += $val; } return (($sum % 10) === 0); }

Kotlin

fun String.luhnAlgorithm() = reversed() .map(Character::getNumericValue) .mapIndexed { index, digit -> when { index % 2 == 0 -> digit digit < 5 -> digit * 2 else -> digit * 2 - 9 } }.sum() % 10 == 0

Oracle PL/SQL

set serveroutput on; declare vpan varchar2(50) := '123456798465'; x varchar2(2):=0; s varchar2(3):=0; begin for i in 1..length(vpan) loop x:= substr(vpan,length(vpan)-i+1,1); if mod(i,2) != 0 then x:=x*2; if x>9 then x:=x-9; end if; end if; s:= s+x; end loop; s:=10-mod(s,10); if s = 10 then s:=0; end if; dbms_output.put_line('luhn= '||s||' card= '||vpan||s); end;

TypeScript

var Moon_Algorithm: any = (setValue: any): boolean => { var ch: number = 0, num: any = String(setValue).replace(/D/g, ''); if ('' === num) return false; for (var i in num) { var n: number = parseInt(num[i], 10); ch += 0 === (i % 2) && 9 < (n *= 2) ? (n - 9) : n; } return 0 == (ch % 10); }



Похожие новости:

Виртуальные номера для регистрации в Вконтакте

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

Индекс автомобильных номеров Чехии

Индекс автомобильных номеров Чехии
Новые регистрационные знаки (с 2001 года) В автомобильных номерах Чехии используются 7 символов (цифры и буквы без диакритических знаков, за исключением G, O, Q, которые можно было бы спутать с C и

Алгоритм Кнута — Морриса — Пратта

Алгоритм Кнута — Морриса — Пратта
Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать

Алгоритм заметающей прямой

Алгоритм заметающей прямой
Алгоритм заметающей прямой или алгоритм выметания плоскости — это алгоритмическая парадигма, которая использует умозрительную выметающую прямую или выметающую поверхность для решения различных задач
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные статьи
Охранное предприятие в Москве – защита и надежность
Охранное предприятие в Москве – защита и надежность
В современном мире, где угрозы личной безопасности и сохранности имущества становятся все более...
Особенности выбора мебели: секреты правильного подбора для интерьера
Особенности выбора мебели: секреты правильного подбора для интерьера
При обустройстве интерьера дома или офиса одним из самых важных аспектов является выбор мебели....
Как купить квартиру в Крыму на стадии котлована: порядок действий и нюансы сделки
Как купить квартиру в Крыму на стадии котлована: порядок действий и нюансы сделки
Инвестирование в недвижимость в Крыму становится все более привлекательным вариантом для тех, кто...
Все новости