卢恩算法
外观
卢恩算法(英语:Luhn algorithm),也称为“模10”(Mod 10)算法,是一种简单的校验和算法,一般用于验证身份识别码,例如发卡行识别码、国际移动设备识别码,美国国家提供商标识号码,或是加拿大社会保险号码。该算法由IBM科学家汉斯·彼得·卢恩创造,专利于1954年1月6日申请,1960年8月23日颁证,美国专利号2950048[1]。
该算法现已属于公有领域并得到了广泛的应用,例如ISO/IEC 7812-1[2]。它不是一种安全的加密哈希函数,设计它的目的只是防止意外出错而不是恶意攻击。
描述
[编辑]卢恩算法会通过校验码对一串数字进行验证,校验码通常会被加到这串数字的末尾处,从而得到一个完整的身份识别码。
我们以数字“7992739871”为例,计算其校验位,设校验位为X并添加至数列末位,即7992739871X:
- 从校验位开始,从右往左,偶数位乘2(例如,7*2=14),然后将两位数字的个位与十位相加(例如,10:1+0=1,14:1+4=5);
- 把得到的数字加在一起(本例中得到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 | =67 |
再用10去减得到校验位 | 3 |
另一种方法是:
- 从校验位开始,从右往左,偶数位乘2,然后将两位数字的个位与十位相加;
- 计算所有数字的和(67);
- 乘以9(603);
- 取其个位数字(3),得到校验位。
优缺点
[编辑]卢恩算法可以发现某一位的错误。 卢恩算法几乎可以发现所有由于邻位上数字被交换产生的错误。 但是,它只能发现数字交换产生的错误中的7/10,不会发现22 ↔ 55, 33 ↔ 66 或 44 ↔ 77。
代码实现
[编辑]Java
[编辑]/**
* 校验位字符集
*/
private static char[] CHECKS = "0987654321".toCharArray();
public static boolean isValidLuhn(String number) {
if (number == null) {
return false;
}
char[] chs = number.toCharArray();
int count = 0;
for (int i = chs.length - 2, k = 1; i >= 0; i--, k++) {
// 不是数字字符时直接返回 false
if (chs[i] < '0' || chs[i] > '9') {
return false;
}
// 偶位数字 * 2,奇位不乘
int num = (chs[i] - '0') << (k & 1);
// 累加
count += num % 10 + num / 10;
}
// 对校验位进行比对
return (chs[chs.length - 1] == CHECKS[count % 10]);
}