Luhn 演算法 (Mod 10) 完整解析：從數學原理到 C/C#/Java 通用實作

前言

Luhn 演算法 (Luhn Algorithm)，又稱「模 10 演算法」，是信用卡號、IMEI、身分證字號、條碼等識別碼廣泛採用的校驗碼標準 (ISO/IEC 7812-1)。本文從數學推導、逐步分解、完整程式碼三個維度徹底講透。

一、演算法規則

1. 從**最右側 (校驗碼位)** 向左，對**偶數位置** (第 2、4、6... 位) 的數字 **乘以 2**
2. 若乘積 ≥ 10，則將十位與個位相加 (等同 `乘積 - 9`)
3. 將所有數字 (含未乘 2 的奇數位) 求和
4. 總和 **模 10 等於 0** 則校驗通過

範例：79927398713 (最後一位 3 為校驗碼)

位置(從右):  1  2  3  4  5  6  7  8  9  10 11
數字:         3  1  7  8  9  3  7  2  9  9  7
乘2(偶數位):     2     16    6     4     18
調整(≥10-9):     2     7      6     4     9
求和: 3 + 2 + 7 + 7 + 9 + 6 + 7 + 4 + 9 + 9 + 9 = 70
70 % 10 = 0 ✓ 合法

二、關鍵數學簡化

對數字 d (0-9) 乘 2 後調整：

• 2*d 若 < 10 → 直接用
• 2*d 若 ≥ 10 → 十位必為 1，個位為 2*d - 10，和為 1 + (2*d - 10) = 2*d - 9

**統一公式**：int doubled = d * 2; int sum = doubled > 9 ? doubled - 9 : doubled;

或查表法 (效能最佳)：int[] lut = {0,2,4,6,8,1,3,5,7,9}; // 索引為原數字，值為處理後結果

三、通用實作 (處理任意長度、字串輸入)

C# 版本

public static class Luhn
{
    private static readonly int[] _doubleMap = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
    
    public static bool Validate(string digits)
    {
        if (string.IsNullOrEmpty(digits)) return false;
        
        int sum = 0;
        bool doubleIt = false; // 從最右側開始，第一位(校驗碼)不乘2
        
        for (int i = digits.Length - 1; i >= 0; i--)
        {
            char c = digits[i];
            if (c < '0' || c > '9') return false; // 非數字直接失敗
            
            int d = c - '0';
            sum += doubleIt ? _doubleMap[d] : d;
            doubleIt = !doubleIt; // 交替
        }
        
        return sum % 10 == 0;
    }
    
    public static char CalculateCheckDigit(string payload)
    {
        int sum = 0;
        bool doubleIt = true; // 校驗碼位為第1位(不乘2)，所以payload最右側為第2位(乘2)
        
        for (int i = payload.Length - 1; i >= 0; i--)
        {
            int d = payload[i] - '0';
            sum += doubleIt ? _doubleMap[d] : d;
            doubleIt = !doubleIt;
        }
        
        int checkDigit = (10 - (sum % 10)) % 10;
        return (char)('0' + checkDigit);
    }
    
    public static string AppendCheckDigit(string payload)
        => payload + CalculateCheckDigit(payload);
}

C/C++ 版本

#include 
#include 
#include 

static const int double_map[10] = {0,2,4,6,8,1,3,5,7,9};

bool luhn_validate(const char *digits)
{
    if (!digits) return false;
    int len = strlen(digits);
    if (len == 0) return false;
    
    int sum = 0;
    bool double_it = false;
    
    for (int i = len - 1; i >= 0; i--)
    {
        char c = digits[i];
        if (!isdigit(c)) return false;
        int d = c - '0';
        sum += double_it ? double_map[d] : d;
        double_it = !double_it;
    }
    return sum % 10 == 0;
}

char luhn_check_digit(const char *payload)
{
    int sum = 0;
    bool double_it = true;
    for (int i = strlen(payload) - 1; i >= 0; i--)
    {
        int d = payload[i] - '0';
        sum += double_it ? double_map[d] : d;
        double_it = !double_it;
    }
    return '0' + (10 - (sum % 10)) % 10;
}

Java 版本

public final class Luhn {
    private static final int[] DOUBLE_MAP = {0,2,4,6,8,1,3,5,7,9};
    
    public static boolean validate(CharSequence digits) {
        if (digits == null || digits.length() == 0) return false;
        int sum = 0;
        boolean doubleIt = false;
        for (int i = digits.length() - 1; i >= 0; i--) {
            char c = digits.charAt(i);
            if (c < '0' || c > '9') return false;
            int d = c - '0';
            sum += doubleIt ? DOUBLE_MAP[d] : d;
            doubleIt = !doubleIt;
        }
        return sum % 10 == 0;
    }
    
    public static char checkDigit(CharSequence payload) {
        int sum = 0;
        boolean doubleIt = true;
        for (int i = payload.length() - 1; i >= 0; i--) {
            int d = payload.charAt(i) - '0';
            sum += doubleIt ? DOUBLE_MAP[d] : d;
            doubleIt = !doubleIt;
        }
        return (char)('0' + (10 - (sum % 10)) % 10);
    }
}

四、進階主題

1. 驗證 vs 產生校驗碼

• 驗證：包含校驗碼的完整字串 → `Validate()`
• 產生：無校驗碼的本體字串 → `CalculateCheckDigit()` → 附加

2. 非數字字元處理

部分標準 (如身分證) 含字母，需先轉換為數字 (如 A=10, B=11... 或特定對應表)，再套用 Luhn。

3. 效能優化

• 查表法 `_doubleMap` 避免分支預測失敗
• 位運算：`(d << 1) - (d >= 5 ? 9 : 0)` 無分支 (視 CPU 而定)
• SIMD 向量化處理超長字串 (信用卡號通常 ≤ 19 位，無需)

4. 常見變體

五、測試向量

[TestCase("79927398713", true)]   // 維基範例
[TestCase("79927398714", false)]  // 錯誤校驗碼
[TestCase("4242424242424242", true)] // Visa 測試卡
[TestCase("1234567812345670", true)] // 通過 Luhn
[TestCase("", false)]
[TestCase("abc", false)]
[TestCase("0", true)]             // 單一 0 合法
public void Validate_ReturnsExpected(string input, bool expected)
{
    Assert.AreEqual(expected, Luhn.Validate(input));
}

六、總結

Luhn 演算法以極簡單的數學規則提供基本防呆能力 (檢測單一數字錯誤、大部分相鄰交換)。核心實作僅需 查表法 + 交替累加 + 模 10。生產代碼建議：

1. 輸入清洗：移除空格/連字號
2. 長度檢查：信用卡 13-19 位
3. 前綴識別：BIN/IIN 判斷卡組織
4. Luhn 校驗：最後一道防線

完整程式碼已整理為可直接複製的跨語言片段，歡迎收藏備用。