Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 27 ноября 2018;
проверки требуют 40 правок.
Алгоритм Лу́на (англ. 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[править | править код]
int sum = 0;
int nDigits = value.length();
int parity = nDigits % 2;
for(int i = nDigits; i > 0; i—){
int digit = Character.getNumericValue(value.charAt(i-1));
if(i%2 == parity){
digit *= 2;
if(digit > 9){
digit -= 9;
}
sum += digit;
}
}
for(int i = nDigits; i > 0; i —){
int digit = Character.getNumericValue(value.charAt(i-1));
if(i % 2 != parity){
sum += digit;
}
}
if((((sum % 10) — 10) * -1) == 10){
return (value + «0»);
}else{
return (value + (((sum % 10) — 10) * -1));
}
}
Примеры реализации[править | править код]
Псевдокод[править | править код]
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 <string.h> // strlen
#include <stdbool.h> // bool
bool checkLuhn(const char *pPurported)
{
int nSum = 0;
int nDigits = strlen(pPurported);
int nParity = (nDigits-1) % 2;
char cDigit[2] = «