盧恩算法

盧恩算法（英語：Luhn algorithm），也稱為「模10」（Mod 10）算法，是一種簡單的校驗和算法，一般用於驗證身份識別碼，例如發卡行識別碼、國際移動設備識別碼，美國國家提供商標識號碼，或是加拿大社會保險號碼。該算法由IBM科學家漢斯·彼得·盧恩創造，專利於1954年1月6日申請，1960年8月23日頒證，美國專利號2950048。

該算法現已屬於公有領域並得到了廣泛的應用，例如ISO/IEC 7812-1。它不是一種安全的加密哈希函數，設計它的目的只是防止意外出錯而不是惡意攻擊。

描述

盧恩算法會通過校驗碼對一串數字進行驗證，校驗碼通常會被加到這串數字的末尾處，從而得到一個完整的身份識別碼。

我們以數字「7992739871」為例，計算其校驗位，設校驗位為X並添加至數列末位，即7992739871X：

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
再用10去減得到校驗位											3

另一種方法是：

1. 從校驗位開始，從右往左，偶數位乘2，然後將兩位數字的個位與十位相加；
2. 計算所有數字的和（67）；
3. 乘以9（603）；
4. 取其個位數字（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]);
}