Luhn算法

Luhn算法

Luhn算法（Luhn algorithm），也稱為“模10”（Mod 10）算法，是一種簡單的校驗和算法，一般用於驗證身份識別碼，例如發卡行識別碼、國際移動設備辨識碼（IMEI），美國國家提供商標識號碼，或是加拿大社會保險號碼。該算法由IBM科學家Hans Peter Luhn創造，專利於1954年1月6日申請，1960年8月23日頒證，美國專利號2950048。

該算法現已屬於公有領域並得到了廣泛的套用，例如ISO/IEC 7812-1。它不是一種安全的加密哈希函式，設計它的目的只是防止意外出錯而不是惡意攻擊。

基本介紹

  • 中文名：Luhn算法
  • 又稱：“模10”（Mod 10）算法
  • 本質：一種簡單的校驗和算法
  • 作用：一般用於驗證身份識別碼
描述,優點和缺點,套用實例,Pseudo-Code,Bash,C,C#,Go,PHP,Java,JavaScript,Python,

描述

Luhn算法會通過校驗碼對一串數字進行驗證，校驗碼通常會被加到這串數字的末尾處，從而得到一個完整的身份識別碼。
我們以數字“7992739871”為例，計算其校驗位：
  1. 從校驗位開始，從右往左，偶數位乘2（例如，1*2=2），然後將兩位數字的個位與十位相加（例如，16：1+6=7，18：1+8=9）；
  2. 把得到的數字加在一起（本例中得到67）；
  3. 將數字的和取模10（本例中得到7），再用10去減（本例中得到3），得到校驗位。
原始數字
7
9
9
2
7
3
9
8
7
1
x
偶數位乘2
7
18
9
4
7
6
9
16
7
2
x
將數字相加
7
9
9
4
7
6
9
7
7
2
x
另一種方法是：
  1. 從校驗位開始，從右往左，偶數位乘2，然後將兩位數字的個位與十位相加；
  2. 計算所有數字的和（67）；
  3. 乘以9（603）；
  4. 取其個位數字（3），得到校驗位。

優點和缺點

Luhn算法將檢測任何單位錯誤，以及幾乎所有相鄰數字的轉置。但是，它不會檢測到兩位數序列09到90的轉置（反之亦然）。它將檢測10個可能的雙誤差中的7個（它不會檢測到22↔55,33↔66或44↔77）。
其他更複雜的校驗位算法（例如Verhoeff算法和Damm算法）可以檢測更多的轉錄錯誤。 Luhn mod N算法是支持非數字字元串的擴展。
因為算法以從右到左的方式對數字進行操作，並且零位僅在它們導致位置偏移時影響結果，所以零填充數字串的開頭不會影響計算。因此，填充到特定位數的系統（例如，通過將1234轉換為0001234）可以在填充之前或之後執行Luhn驗證並獲得相同的結果。
在0到奇數長度之前，可以從左到右而不是從右到左處理數字，使奇數位數加倍。
該算法出現於美國專利中，用於計算校驗和的手持式機械設備。因此需要相當簡單。該裝置通過機械手段獲得了模數10。替換數字，即double和reduce過程的結果，不是機械地產生的。相反，數字在機器的主體上以其置換順序標記。

套用實例

Pseudo-Code

  function checkLuhn(string purportedCC) {
    int sum := integer(purportedCC[length(purportedCC)-1])
    int nDigits := length(purportedCC)
    int parity := nDigits modulus 2
    for i from 0 to nDigits - 2 {
        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
  }

Bash

#!/bin/bash
 
strip_last() {
    echo ${1:$((${#1}-1)):1}
}
 
NUMBER=$1
NUM_DIGITS=${#NUMBER}
ODD_INDEX_MODIFIER=$(( ${NUM_DIGITS} % 2 ))
INDEX=1
TOTAL_NON_CHECK=0
while read -n1 DIGIT; do # read 1 character
    if [ $(( (${ODD_INDEX_MODIFIER} + ${INDEX}) % 2 )) -eq 0 ]; then
        # Even index relative to least significant digit LSD
        TMP=$(( ${DIGIT} * 2 ))
        if [ ${TMP} -ge 10 ]; then
                TMP=$(( ${TMP} - 9))
        fi
        TOTAL_NON_CHECK=$((${TOTAL_NON_CHECK} + ${TMP}))
    else
        TOTAL_NON_CHECK=$((${TOTAL_NON_CHECK} + ${DIGIT}))
    fi
    INDEX=$((${INDEX} + 1))
done < <(echo -n "$NUMBER")
 
NON_CHECK_LAST_DIGIT=$(strip_last ${TOTAL_NON_CHECK})
if [ ${NON_CHECK_LAST_DIGIT} -eq 0 ]; then
    LUHN_CHECK_DIGIT=0
else
    LUHN_CHECK_DIGIT=$(( 10 - ${NON_CHECK_LAST_DIGIT} ))
fi
 
echo "${LUHN_CHECK_DIGIT}"

C

  #include <stdlib.h> // atoi
  #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] = "\0";
    for (int i = nDigits; i > 0 ; i--)
    {
      cDigit[0]  = pPurported[i-1];
      int nDigit = atoi(cDigit);
 
      if (nParity == i % 2)
        nDigit = nDigit * 2;
 
      nSum += nDigit/10;
      nSum += nDigit%10;
    }
    return 0 == nSum % 10;
  }

C#

   public static bool checkLuhn(string data) {
      int sum = 0;
      int len = data.Length;
      for(int i = 0; i < len; i++) {
         int add = (data[i] - '0') * (2 - (i + len) % 2);
         add -= add > 9 ? 9 : 0;
         sum += add;
      }
      return sum % 10 == 0;
   }

Go

func checkLuhn(purportedCC string) bool {
var sum = 0
var nDigits = len(purportedCC)
var parity = nDigits % 2
 
for i := 0; i < nDigits; i++ {
var digit = int(purportedCC[i] - 48)
if i%2 == parity {
digit *= 2
if digit > 9 {
    digit -= 9
    }
}
sum += digit
}
return sum%10 == 0
}

PHP

<?php
function luhn($input) {
$input = strrev(preg_replace('/\\D+/', '', $input));
if ($input == '') {
return false;
}
$total = 0;
for ($i = 0, $n = strlen($input); $i < $n; $i++) {
$total += $i % 2 ? 2 * $input[$i] - ($input[$i] > 4 ? 9 : 0) : $input[$i];
}
return !($total % 10);
}
?>

Java

   public static boolean check(int[] digits) {
       int sum = 0;
       int length = digits.length;
       for (int i = 0; i < length; i++) {
 
           // get digits in reverse order
           int digit = digits[length - i - 1];
 
           // every 2nd number multiply with 2
           if (i % 2 == 1) {
               digit *= 2;
           }
           sum += digit > 9 ? digit - 9 : digit;
       }
       return sum % 10 == 0;
   }

JavaScript

function luhn(num) {
num = (num + '').replace(/\D+/g, '').split('').reverse();
if (!num.length) {
return false;
}
var total = 0, i;
for (i = 0; i < num.length; i++) {
num[i] = parseInt(num[i]);
total += i % 2 ? 2 * num[i] - (num[i] > 4 ? 9 : 0) : num[i];
}
if (total === 0) {
return false;
}
return (total % 10) == 0;
}

Python

def checkLuhn(purportedCC=''):
    sum_ = 0
    parity = len(purportedCC) % 2
    for i, digit in enumerate([int(x) for x in purportedCC]):
        if i % 2 == parity:
            digit *= 2
            if digit > 9:
                digit -= 9
        sum_ += digit
    return sum_ % 10 == 0

相關詞條

熱門詞條

聯絡我們