Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




01.12.2021


01.12.2021


01.12.2021


01.12.2021


30.11.2021


30.11.2021


30.11.2021





Яндекс.Метрика

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

27.10.2021

Алгоритм Луна (англ. 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); }



Имя:*
E-Mail:
Комментарий: