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

Алгоритм Лу́на (англ. 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, то исходные данные верны.

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

Go

// CalculateLuhn return the check number
func CalculateLuhn(number int) int {
	checkNumber := checksum(number)

	if checkNumber == 0 {
		return 0
	}
	return 10 - checkNumber
}

func checksum(number int) int {
	var luhn int

	for i := 0; number > 0; i++ {
		cur := number % 10

		if i%2 == 0 { // even
			cur = cur * 2
			if cur > 9 {
				cur = cur%10 + cur/10
			}
		}

		luhn += cur
		number = number / 10
	}
	return luhn % 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 % 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;
}

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

Go

 // Valid check number is valid or not based on Luhn algorithm
func Valid(number int) bool {
	return (number%10+checksum(number/10))%10 == 0
}

func checksum(number int) int {
	var luhn int

	for i := 0; number > 0; i++ {
		cur := number % 10

		if i%2 == 0 { // even
			cur = cur * 2
			if cur > 9 {
				cur = cur%10 + cur/10
			}
		}

		luhn += cur
		number = number / 10
	}
	return luhn % 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++

bool checkLuhn(std::string input) {
    int sum = 0;

    for (int i = input.length() - 1; i >= 0; i--) {
        int 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 + 1) % 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 integer;
    s integer:=0;
begin
    for i in 1..length(vpan)
    loop
        x:= to_number(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= '||to_char(s)||' card= '||vpan||to_char(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.

Ссылки

• Описание алгоритма Луна и нескольких других способов вычисления контрольной цифры.