Алгоритм Луна
Алгоритм Лу́на (англ. 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
private static boolean isValidLuhn(String value) {
int sum = Character.getNumericValue(value.charAt(value.length() - 1));
int parity = value.length() % 2;
for (int i = value.length() - 2; i >= 0; i--) {
int summand = Character.getNumericValue(value.charAt(i));
if (i % 2 == parity) {
int product = summand * 2;
summand = (product > 9) ? (product - 9) : product;
}
sum += summand;
}
return (sum % 10) == 0;
}
C
#include <string.h> // заголовок, объявляющий функцию strlen()
int luhn(const char * card_number) // принимаем в аргументы номер карты
{
int len = strlen(card_number); // узнаем длину номера карты
int digit = 0; // текущая цифра в цикле (см. ниже)
int check_digit = 0; // переменная, которая будет хранить проверочную цифру
int i;
for (i = len - 1; i >= 0; --i) // главный цикл, в процессе него вычисляется проверочная цифра
{
digit = card_number[i] - '0'; // переводим цифру из char в int
if (i % 2 == 0) // если позиция цифры чётная, то:
{
digit *= 2; // умножаем цифру на 2
if (digit > 9) // согласно алгоритму, ни одно число не должно быть больше 9
digit -= 9; // второй вариант сведения к единичному разряду
}
check_digit += digit; // прибавляем к check_digit номера согласно алгоритму
}
return (check_digit * 9) % 10; // возвращаем проверочное число, вычисленное согласно алгоритму
}
C++
#include <string>
int luhn(std::string const & input)
{
int check_digit = 0;
bool odd = false;
for (auto it = input.rbegin(); it != input.rend(); ++it)
{
auto digit = *it - '0';
if ((odd = !odd))
{
digit *= 2;
if (digit > 9)
digit -= 9;
}
check_digit += digit;
}
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 & 1) == 0) // если позиция цифры чётная, то:
{
number *= 2; // умножаем цифру на 2
if(number > 9) // согласно алгоритму, ни одно число не должно быть больше 9
{
number -= 9; // второй вариант сведения к единичному разряду
}
}
sum += number; // прибавляем к sum номера согласно алгоритму
if(sum >= 10) // если сумма больше либо 10
{
sum -= 10; // вычитаем из суммы 10, т. к. последняя цифра не изменится
}
}
return sum == 0; // вернуть, равна ли последняя цифра нулю
}
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) := '2345698465';
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);
}
Источники информации
- U.S. Patent 2 950 048 Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.