Luhn演演算法
Luhn演演算法
Luhn演演算法（Luhn algorithm），也稱為“模10”（Mod 10）演演算法，是一種簡單的校驗和演演算法，一般用於驗證身份識別碼，例如發卡行識別碼、國際移動設備辨識碼（IMEI），美國國家提供商標識號碼，或是加拿大社會保險號碼。該演演算法由IBM科學家Hans Peter Luhn創造，專利於1954年1月6日申請，1960年8月23日頒證，美國專利號2950048。
該演演算法現已屬於公有領域並得到了廣泛的應用，例如ISO/IEC 7812-1。它不是一種安全的加密哈希函數，設計它的目的只是防止意外出錯而不是惡意攻擊。
Luhn演演算法會通過校驗碼對一串數字進行驗證，校驗碼通常會被加到這串數字的末尾處，從而得到一個完整的身份識別碼。
我們以數字“7992739871”為例，計算其校驗位：
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 |
另一種方法是：
1.從校驗位開始，從右往左，偶數位乘2，然後將兩位數字的個位與十位相加；
2.計算所有數字的和（67）；
3.乘以9（603）；
4.取其個位數字（3），得到校驗位。
Luhn演演算法將檢測任何單位錯誤，以及幾乎所有相鄰數字的轉置。但是，它不會檢測到兩位數序列09到90的轉置（反之亦然）。它將檢測10個可能的雙誤差中的7個（它不會檢測到22↔55,33↔66或44↔77）。
其他更複雜的校驗位演演算法（例如Verhoeff演演算法和Damm演演算法）可以檢測更多的轉錄錯誤。 Luhn mod N演演算法是支持非數字字元串的擴展。
因為演演算法以從右到左的方式對數字進行操作，並且零位僅在它們導致位置偏移時影響結果，所以零填充數字串的開頭不會影響計算。因此，填充到特定位數的系統（例如，通過將1234轉換為0001234）可以在填充之前或之後執行Luhn驗證並獲得相同的結果。
在0到奇數長度之前，可以從左到右而不是從右到左處理數字，使奇數位數加倍。
該演演算法出現於美國專利中，用於計算校驗和的手持式機械設備。因此需要相當簡單。該裝置通過機械手段獲得了模數10。替換數字，即double和reduce過程的結果，不是機械地產生的。相反，數字在機器的主體上以其置換順序標記。
基本信息
- 本質
- 一種簡單的校驗和演算法