룬 알고리즘

Luhn 알고리즘 또는 Luhn 공식은 생성자인 IBM 과학자 Hans Peter Luhn의 이름을 따서 명명된 "계수 10" 또는 "모드 10" 알고리즘으로도 알려져 있으며 다양한 식별 번호를 검증하는 데 사용되는 간단한 체크 디짓 공식입니다.

1960년 ^[1]8월 23일에 부여된 미국 특허 제2,950,048호에 기재되어 있습니다.

이 알고리즘은 퍼블릭 도메인에 있으며 오늘날 널리 사용되고 있습니다.ISO/IEC 7812-1에 ^[2]명시되어 있습니다.이 기능은 암호화된 보안 해시 함수가 아니라 악의적인 공격이 아닌 우발적인 오류로부터 보호하도록 설계되었습니다.대부분의 신용 카드와 많은 정부 식별 번호는 유효한 번호와 잘못 입력되었거나 잘못된 번호를 구별하는 간단한 방법으로 알고리즘을 사용합니다.

묘사

체크 디짓은 다음과 같이 계산됩니다.

1. 번호에 이미 체크 디짓이 포함되어 있으면 해당 디짓을 드롭하여 "페이로드"를 형성합니다.체크 디짓은 대부분 마지막 디짓입니다.
2. 페이로드의 경우 맨 오른쪽 자리부터 시작합니다.왼쪽으로 이동하여 모든 두 번째 자리(맨 오른쪽 자리 포함)의 값을 두 배로 늘립니다.
3. 결과 자릿수의 값을 합합니다.
4. 체크 디짓은 (${\displaystyle \mathrm{10}-}$ (${\displaystyle s}$ mod ${\displaystyle }$ ${\displaystyle 10}$) mod ⁡ ${\displaystyle 10}${\$displaystyle$ ($10-(s$\operator$name {mod}$ 10)\$operator name {mod}$ 10$\}$에 의해 계산됩니다.이 숫자는 10의 배수를 만들기 위해 s${displaystyle}$에 추가해야 하는 최소 숫자(0일 수 있음)입니다.동일한 값을 제공하는 다른 유효한 $공식$은 9${\displaystyle }$-${\displaystyle }$($s$${\displaystyle }$+${\displaystyle 9}$ ) mod$$${\displaystyle }$${\displaystyle 10}$ )$${\$displaystyle 9-(s$+ $9)\operatorname {mod$$\}\},$ (${\displaystyle 10}$ ${\displaystyle -s}$ ) mod ${\displaystyle }$$$$\displaystyle$ $(10-s)$ \$operatorname {mod$ 및 $10 ⌈$/ ${\displaystyle 10}$ $s$ (10 -$$s )입니다.모듈로 연산에 의해 음수가 처리되는 방식의 차이로 인해 (${\displaystyle 10}$ ${\displaystyle -s}$ ) ${\displaystyle \mathrm{mod}}$ ${\displaystyle }$ ${displaystyle (10-s)\operator$name {$mod} 10$$}$ 공식이 모든 환경에서 작동하지는 않습니다.

체크 디짓 계산 예제

계정 번호 7992739871의 예("payload"만 해당, 체크 디짓 미포함)를 가정합니다.

결과 숫자의 합은 67입니다.

확인 숫자는 10${\displaystyle }$- (${\displaystyle \mathrm{67}}$ mod ${\displaystyle }$ ${\displaystyle 10}$ ${\displaystyle )}$ $=$ ${\displaystyle 3}${\$displaystyle 10-(67\operator$name {$mod} 10$)=$3$과 ${\displaystyle \mathrm{같습니다}}$.

이렇게 하면 전체 계좌 번호가 79927398713으로 표시됩니다.

체크 디짓 유효성 검사 예제

1. 유효성을 검사할 숫자의 체크 자릿수(마지막 자릿수)를 놓습니다.(예: 79927398713 -> 79927398771)
2. 체크 디짓 계산(위 참조)
3. 결과를 원래 체크 디짓과 비교합니다.두 숫자가 일치하면 결과가 유효합니다.(${\displaystyle 예}$ (${\displaystyle \mathrm{주어진}}$ ${\displaystyle \mathrm{체크}}$ ${\displaystyle \mathrm{디짓}}$ $=$ ${\displaystyle \mathrm{계산}}$된 ${\displaystyle \mathrm{체크}}$ ${\displaystyle \mathrm{디짓})}$ ${\displaystyle \iff }$ (${\displaystyle \mathrm{유효}}$한 ${\displaystyle \mathrm{체크}\mathrm{디짓}}$임$)$ {\$displaystyle (주어진$ 체크 디짓 = $가속$된 체크$$디짓)$\왼쪽$ 오른쪽 화살표$(ValidCheckDigit)}.$

장점과 단점

Luhn 알고리즘은 인접한 숫자의 거의 모든 위치뿐만 아니라 모든 한 자릿수 오류를 감지합니다.그러나 두 자리 시퀀스 09 ~ 90(또는 그 반대)의 전위는 감지하지 못합니다.가능한 대부분의 쌍둥이 오류를 탐지합니다(22 ↔ 55, 33 ↔ 66 또는 44 ↔ 77).

Verhoeff 알고리즘 및 Damm 알고리즘과 같은 더 복잡한 체크 디짓 알고리즘은 더 많은 전사 오류를 탐지할 수 있습니다.Luhn mod N 알고리즘은 숫자가 아닌 문자열을 지원하는 확장입니다.

알고리즘이 오른쪽에서 왼쪽으로 숫자에 대해 작동하고 숫자 0이 위치 이동을 유발하는 경우에만 결과에 영향을 미치므로 숫자 문자열의 시작 부분을 0으로 패딩해도 계산에 영향을 주지 않습니다.따라서 (예를 들어 1234를 0001234로 변환하여) 특정 자릿수로 패딩하는 시스템은 패딩 전후에 Lunn 유효성 검사를 수행하여 동일한 결과를 얻을 수 있습니다.

이 알고리즘은 체크섬을 계산하기 위한 간단한 휴대용 기계 장치를 위해 미국^[1] 특허에 등장했습니다.그 장치는 기계적인 방법으로 모드 10 합을 취했습니다.대체 자릿수, 즉 이중 및 축소 절차의 결과가 기계적으로 생성되지 않았습니다.대신, 기계 본체에 숫자가 순열로 표시되었습니다.

의사 코드 구현

다음 함수는 체크 디짓을 포함한 카드 번호를 정수 배열로 사용하고 체크 디짓이 맞다면 true를 출력하고 그렇지 않으면 false를 출력합니다.

함수가 유효합니다(cardNumber[1].length]) sum : = 0 parity : = length mod 2 for if i mod 2 != parity if 1 to length do if if card Number[i] > 4이면 sum : = sum + 2 * card Number[i]이고, return card Number[length]가 종료되면 sum : == (sum 10 - (s mod 10) 종료 기능

코드 구현

C#

쿨한 유효한 Luhn입니다.(에 인트[] 숫자들) {     인트 체크_자리수 = 0;     위해서 (인트 i = 숫자들.길이 - 2; i >= 0; --i)         체크_자리수 += ((i & 1) 이라 0) 스위치         {             진실의  => 숫자들[i] > 4 ? 숫자들[i] * 2 - 9 : 숫자들[i] * 2,             거짓의 => 숫자들[i]         };      돌아가다 10 - (체크_자리수 % 10) == 숫자들.지난(); } 

사용하다

Luhn 알고리즘은 다양한 시스템에서 사용됩니다.

• 신용카드번호
• IMEI 번호
• 미국의 국가 제공자 ID 번호
• 캐나다의 사회 보험 번호
• 이스라엘 ID 번호
• 남아프리카 공화국 ID 번호
• 스웨덴어 주민등록번호.
• 스웨덴 기업 ID 번호(OrgNr)
• 그리스 사회 보장 번호(αμκα)
• SIM 카드 번호
• 유럽 특허 출원 번호
• 맥도날드, 타코 벨, 트랙터 서플라이 Co. 영수증에 표시되는 조사 코드

레퍼런스

외부 링크

• 로제타 코드 프로젝트에서 150개 언어로 구현