Luhn算法,(鲁恩/卢恩算法 )也被称作“模10算法”(Mod 10)。是由IBM科学家Hans Peter Luhn发明的一种简单的校验和计算算法。主要用来计算信用卡、银行卡、社保卡号、会员卡号、设备IMEI、部分手机ICCID等号码的合法性。
Luhn算法会通过校验码对一串数字进行验证,校验码通常会被加到这串数字的末尾处,从而得到一个完整的身份识别码。
算法介绍
1、算上校验位数字从右向左开始,偶数位乘以2,如果乘以2的结果是两位数,将两个位上数字相加保存
2、把所有数字相加,得到总和
3、如果总和可以被10整除,则号码合法,反之不合法。
英文原文描述:
1.Counting from the check digit, which is the rightmost, and moving left, double the value of every second digit.
2.Sum the digits of the products (e.g., 10: 1 + 0 = 1, 14: 1 + 4 = 5) together with the undoubled digits from the original number.
3.If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.
优点和缺点
Luhn 算法会检测到任何单码的错误以及几乎所有的相邻数字换位的错误。但是它不会检测两个数字序列09转90的错误(反之亦然)。它会检测到十分之七的相同双位数错误(不会检测到22和55的互换,33和66的互换,44和77的互换)。其他更复杂的检查数字算法,如费尔赫夫算法,可以检测出更多的转录错误。模N的Luhn算法是Luhn算法的一个扩展,支持非数字字符串。因为该算法采取了从右向左的方式,而且零位会影响计算的结果。只有当零位造成了数位的移动或是用零来填充一串数字的开头时才不会影响计算结果的生成。因此不论在将1234用零填充为0001234之前或是之后,使用Luhn算法得到的结果都是一样的。
该算法在美国专利上是为了给手持或是机械设备计算校验码。所以它必须尽可能的简单。
举例使用
根据定义我们可以反推回去计算最后一位数字:
我们以数字“1234567890x”为例。求解其校验位 x :
1、使待校验数字串符合Luhn算法;
从右至左,偶数位乘2,大于10则个位与十位数相加,得到数字字符串:
1,4,3,8,5,3,7,7,9,0,x
2、数字字符串相加求和,使之满足“模10算法”即可
1+4+3+8+5+3+7+7+9 + x = 47 + x
(47 + x)%10 = 0
x=3
有公式算出校验位为 3
程序实现
以PHP语言为例,计算校验位的值:
function getLuhnCheckDigit(string $payload){
$payload = $payload;
// echo "payload: {$payload}\n";
$payload = strrev($payload);
$payload = str_split($payload);
$len = count($payload) - 1;
$sum = 0;
for ($i = 0; $i <= $len; $i++){
$num = $payload[$i];
// 非数字忽略
if(!is_numeric($num)) continue;
// 偶数位
if($i % 2 == 0){
$num = $num * 2;
if($num >= 10){
$list = str_split($num);
$num = array_sum($list);
}
}
$sum += $num;
}
// echo "sum: $sum\n";
$checkDigit = (10 - ($sum % 10)) % 10;
return $checkDigit;
}
echo getLuhnCheckDigit(substr('89860622370032865582', 0, -1)) . "\n";
echo getLuhnCheckDigit(substr('8965880812100011146', 0, -1)) . "\n";
echo getLuhnCheckDigit(substr('865771050598853', 0, -1)) . "\n";
echo getLuhnCheckDigit(substr('868039050078079', 0, -1)) . "\n";
echo getLuhnCheckDigit('1234567890') . "\n";
文章部分节选自互联网,略有删改;
该算法通常用于:手机/物联网卡iccid校验位计算、设备号imei校验位计算、银行卡号校验位计算、信用卡校验位计算、会员卡校验位计算【中国移动的ICCID制卡时末位不一定是校验位】
Luhn check digit algorithm / Luhn checksum calculate
参考文章:
https://en.wikipedia.org/wiki/Luhn_algorithm
ICCID checksum (smartjac.biz)