卢恩算法

卢恩算法（），也称为“模10”（Mod 10）算法，是一种简单的校验和算法，一般用于验证身份识别码，例如发卡行识别码、国际移动设备识别码，美国号码，或是。该算法由IBM科学家创造，专利于1954年1月6日申请，1960年8月23日颁证，美国专利号2950048专利 US2950048 - COMPUTER FOR VERIFYING NUMBERS  -  Google 专利。

该算法现已属于公有领域并得到了广泛的应用，例如ISO/IEC 7812-1。它不是一种安全的加密哈希函数，设计它的目的只是防止意外出错而不是恶意攻击。

 描述 
卢恩算法会通过校验码对一串数字进行验证，校验码通常会被加到这串数字的末尾处，从而得到一个完整的身份识别码。

我们以数字“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 将数字相加7994769772=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]);
}

参见
 国际商品编码#校驗碼的計算方法

参考文献

Category:同余
Category:校验和算法
Category:错误检测与校正