-
Luhn算法
鎖定
Luhn算法描述
Luhn算法會通過校驗碼對一串數字進行驗證，校驗碼通常會被加到這串數字的末尾處，從而得到一個完整的身份識別碼。
我們以數字“7992739871”為例，計算其校驗位：
- 從校驗位開始，從右往左，偶數位乘2（例如，1*2=2），然後將兩位數字的個位與十位相加（例如，16：1+6=7，18：1+8=9）；
- 把得到的數字加在一起（本例中得到67）；
- 將數字的和取模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 |
另一種方法是：
- 從校驗位開始，從右往左，偶數位乘2，然後將兩位數字的個位與十位相加；
- 計算所有數字的和（67）；
- 乘以9（603）；
- 取其個位數字（3），得到校驗位。
Luhn算法優點和缺點
Luhn算法將檢測任何單位錯誤，以及幾乎所有相鄰數字的轉置。但是，它不會檢測到兩位數序列09到90的轉置（反之亦然）。它將檢測10個可能的雙誤差中的7個（它不會檢測到22↔55,33↔66或44↔77）。
其他更復雜的校驗位算法（例如Verhoeff算法和Damm算法）可以檢測更多的轉錄錯誤。 Luhn mod N算法是支持非數字字符串的擴展。
因為算法以從右到左的方式對數字進行操作，並且零位僅在它們導致位置偏移時影響結果，所以零填充數字串的開頭不會影響計算。因此，填充到特定位數的系統（例如，通過將1234轉換為0001234）可以在填充之前或之後執行Luhn驗證並獲得相同的結果。
在0到奇數長度之前，可以從左到右而不是從右到左處理數字，使奇數位數加倍。
該算法出現於美國專利
[2]
中，用於計算校驗和的手持式機械設備。因此需要相當簡單。該裝置通過機械手段獲得了模數10。替換數字，即double和reduce過程的結果，不是機械地產生的。相反，數字在機器的主體上以其置換順序標記。
Luhn算法應用實例
Luhn算法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
}
Luhn算法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}"
Luhn算法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;
}
Luhn算法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;
}
Luhn算法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
}
Luhn算法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);
}
?>
Luhn算法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;
}
Luhn算法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;
}
Luhn算法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
