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（例如，7*2=14），然後將兩位數字的個位與十位相加（例如，10：1+0=1，14：1+4=5）；
  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
=67
另一種方法是：
  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=$1NUM_DIGITS=${#NUMBER}ODD_INDEX_MODIFIER=$(( ${NUM_DIGITS} % 2 ))INDEX=1TOTAL_NON_CHECK=0while 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=0else    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 = 0var nDigits = len(purportedCC)var parity = nDigits % 2 for i := 0; i < nDigits; i++ {var digit = int(purportedCC[i] - 48)if i%2 == parity {digit *= 2if digit > 9 {    digit -= 9    }}sum += digit}return sum%10 == 0}

PHP

<?phpfunction 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

相關詞條

熱門詞條

聯絡我們