身份證號的末位校驗碼演算法最後一步模11是基於什麼考慮？

01-03

演算法：
http://zh.wikipedia.org/wiki/%E4%B8%AD%E5%8D%8E%E4%BA%BA%E6%B0%91%E5%85%B1%E5%92%8C%E5%9B%BD%E5%85%AC%E6%B0%91%E8%BA%AB%E4%BB%BD%E5%8F%B7%E7%A0%81
如果模10，就不會出現X結尾的身份證號了，豈不是更有利於社會和諧？當初設計這個演算法的人是怎麼想的呢？

不邀自答。

我本來計劃把身份證號的校驗碼演算法的分析放在我正在撰寫的知乎電子書《質數了不起》的紙質擴展版書籍中的，但不曾想類似的問題推到了時間線上。思前想後，還是準備優先以解答問題為主。本答案部分內容的修改版本將會放在紙質擴展版書籍中。

本答案寫的有點亂，並且有點偏數學。所以還是等我紙質版書寫完，再看紙質版上的原理解釋吧…

需要的數學知識

身份證驗證碼需要這樣一個數學原理：如果兩個正整數 $m$ 、 $n$ 互質，則一定存在兩個整數 $a_m$ 、 $a_n$ （不一定是正整數），使得：

$m cdot a_m+n cdot a_n=1$

在此我就不嚴格證明這個性質了，據說現在參加奧林匹克數學競賽的初中生似乎就要學習這個數學原理。我們接下來要了解，從這個數學原理出發，能得到哪些有意思的性質。

我們假設 $m>n$ ，現在，令上式左右兩邊同時取模 $m$ （簡單來說，對一個整數取模 $m$ ，是指求這個整數除以 $m$ 後所得到的餘數），得到：

$m cdot a_m + n cdot a_n equiv 1 (mod m)$

前面提到，模運算就是求餘數。注意到由於 $m,a_m$ 都是整數，所以 $m cdot a_m$ 除以 $m$ 的餘數一定為0，即有：

$m cdot a_m equiv 0 (mod m)$

所以我們可以得到：

$n cdot a_n equiv 1 (mod m)$

雖然不太直觀，但我們可以得到這樣一個有趣的性質：如果 $m,n$ 互質，則一定存在一個 $0 < a_n < n$ 的數，使得在模 $m$ 條件下，這個數和 $n$ 相乘的結果為1。注意到這個性質和我們一般情況下認為的「倒數」概念很像。本來嘛，倒數的定義就是和原數相乘等於1的數，只不過這裡是在模 $m$ 的條件下等於1的。在模 $m$ 的條件下，一般會把 $a_n$ 寫成 $n^{-1}$ 。

身份證號校驗演算法

先來看看身份證號的校驗演算法。首先，對身份證號的各個位設置一個對應的「權重值」。這個所謂的權重值對於所有的身份證號都是一樣的。根據《中華人民共和國國家標準GB11643-1999》，每一位對應的「權重值」如下表所示：

序號 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 權重 07 09 10 05 08 04 02 01 06 03 07 09 10 05 08 04 02 01

隨後，把身份證號的各個位乘以對應的權重值後（如果末位是X，則對應位為10），把結果相加模11，如果餘數為1，則身份證號驗證通過。用數學公式表示為：令身份證號從前至後的18位分別為 $a_{18},a_{17}, cdots, a_1$ ，身份證號對應位的權重分別為 $W_{18},W_{17},cdots,W_{1}$ ，則校驗演算法驗證下述等式是否成立：

$a_{18} cdot W_{18} + a_{17} cdot W_{17} + cdots + a_1 cdot W_1 overset{?}{equiv} 1 (mod 11)$

（為了論述方便，後面的公式中會略去mod 11符號）我們用《中華人民共和國國家標準GB11643-1999》中給出的例子來驗證一下。例子中給出的居民身份證號為11010519491231002X。各個位的序號、權重、號碼如下表所示：

序號 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 權重 07 09 10 05 08 04 02 01 06 03 07 09 10 05 08 04 02 01 號碼 01 01 00 01 00 05 01 09 04 09 01 02 03 01 00 00 02 10

驗證式為：

$7cdot1+9cdot1+10cdot0 + 5cdot1 + 8cdot0 + 4cdot5 + 2cdot1 + 1cdot9 + 6cdot4 + 3cdot9 + 7cdot1 + 9cdot2 + 10cdot3 + 5cdot1 + 8cdot0 + 4cdot0 + 2cdot2 + 1cdot10 equiv 1$

身份證號校驗演算法的功能

前面的很多答主也提到了，身份證號校驗演算法的功能有3個：

如果身份證號碼的其中一位填錯了（包括最後一個校驗位），則校驗演算法可以檢測出來。
如果我們知道身份證號碼的哪一位填錯了，應用校驗演算法可以快速得知填錯那一位正確的值應該是多少。（感謝 @劉天任指出，這條性質實際上是第1條性質的推論。從編碼理論角度，身份證號校驗碼並不是糾錯碼，糾錯碼應該可以「不知道具體哪位錯了的條件下糾正錯誤」。不過，末尾「擴展」部分會用到這個推論，所以這裡仍然保留。）
（ @劉天任給出）如果身份證號的相鄰2位填反了，則校驗演算法可以檢測出來。

下面，我們用前面提到的原理分析一下為何有上述3個性質。

身份證號驗證演算法背後的數學原理

如果身份證號碼的其中一位填錯了（包括最後一個校驗位），則校驗演算法可以檢測出來

相信大家很容易了理解第一個功能：如果身份證號中有一位輸入錯誤，則校驗等式左邊的結果一定會發生變化，校驗等式就不成立了。

如果我們知道身份證號碼的哪一位填錯了，應用校驗演算法可以快速得知填錯那一位正確的值應該是多少

第二個功能需要稍微分析一下。假定我們已經知道第 $i$ 位輸入錯誤了，而其它位都是正確的，實際上我們需要求解一個模11下的方程：

$sum_{j=1,j eq i}^{18}{a_j cdot W_j} + a_i cdot W_i equiv 1$

整理一下，有：

$a_i cdot W_i equiv 1 - sum_{j=1,j eq i}^{18}{a_j cdot W_j}$

注意前面的性質，由於11是個質數，而根據設置的權重值， $W_i < 11$ ，因此我們一定能夠找到一個 $W_i^{-1}$ ，使得 $W_i cdot W_i^{-1} equiv 1$ 。因此，我們在方程兩邊同時乘以 $W_i^{-1}$ ，得到：

$a_i equiv W_i^{-1} cdot left(1 - sum_{j=1,j eq i}^{18}{a_j cdot W_j} ight)$

根據這個公式，我們可以把所有對應的數字代入到等式右邊，從而得到輸入錯誤位所對應的正確結果是多少。

如果身份證號的相鄰2位填反了，則校驗演算法可以檢測出來

我們來看看，如果填反了會發生什麼情況。假設兩個相鄰位為 $a_{i+1},a_{i}$ ，如果填反了且校驗等式仍然驗證通過，則一定有：

$a_{i+1} cdot W_{i+1} + a_icdot W_i = a_{i+1} cdot W_i + a_i cdot W_{i+1}$

整理一下，得到：

$a_icdot (W_i - W_{i+1}) equiv a_{i+1} cdot (W_{i} - W_{i+1})$

我們來觀察一下《中華人民共和國國家標準GB11643-1999》的規範。仔細觀察會發現，從後到前，對應的權重分別是 $1 equiv 2^0$ ， $2 equiv 2^1$ ， $4 equiv 2^2$ ， $8 equiv 2^3$ ， $5 equiv 2^4$ ，......， $7 equiv 2^{17}$ 。也就是說， $a_i equiv 2^{i-1}$ 。代入上式，有：

$a_icdot (2^{i-1} - 2^i) equiv a_{i+1} cdot (2^{i-1} - 2^i)$

兩邊同時除以 $2^{i-1}$ ，得到：

$a_icdot (1 - 2) equiv a_{i+1} cdot (1- 2)$

也就是說： $a_i = a_{i+1}$ ，即只有當相鄰位上的數相等時，填反了驗證等式才會通過。但是相鄰位上的數如果都相等了，填反了也沒關係嘛。

實際上，如果有抽象代數基礎的話會知道2是 $mathbb{Z}_{11}$ 下的生成元。而且，不難證明，只要權重是根據生成元的指數冪選取的，都可以解決相鄰位填反驗證等式不通過的功能。

模10是不是更好？

模10可以滿足身份證號前面的兩個性質。觀察公式：

$a_i equiv W_i^{-1} cdot left(1 - sum_{j=1,j eq i}^{18}{a_j cdot W_j} ight)$

如果要滿足身份證驗證演算法的功能，我們實際上只需要要求 $W_i$ 與模數互質就可以了。 @劉天任給出的模10演算法中，權重值分別為1、3、7、9，都是與10互質的數。

但是，模10比模11缺少了第三個功能：模10不能防止身份證的相鄰2位填反了。這本質原因是模10下形成的有限域 $mathbb{Z}_{10}$ 只包含與10互質的整數1、3、7、9。這導致的一個後果是：當存在2個及以上位錯誤時，模10不能保證90%的檢測概率。這個結論討論起來就有點複雜了，感興趣的知友們可以簡單思考一下為什麼。

總結

從理論上看，選擇模11的本質原因是儘可能允許驗證演算法可以覆蓋到常見的身份證填錯情況。而身份證填錯的常見情況就是：

有一個數填錯了。
相鄰兩位填反了。

注意，技術不是萬能的，對於更多可能的情況，身份證校驗演算法大多數是無法校驗出來的。不過，理論分析可以得到這樣一個結論：如果有2個以上的位填寫錯誤，而填寫錯誤不是刻意而為之，而是隨機填錯了的話，則身份證校驗演算法能夠檢測出錯誤的概率為90%。

如果以數學為武器，看清身份證號驗證原理的話，怎麼設置都會繞不開基本問題的…

擴展

知友們可以思考這樣一個問題：如果某個平台公開了一部分身份證號碼，但是身份證號碼只隱藏了出生年份，例如：110105????1231002X。這樣隱藏是對的嗎？會帶來什麼風險？進一步，如果我們僅能隱藏4位的話，隱藏哪4位會更安全一些呢？

以上。

甲：「你今兒發生什麼事兒了，那麼難過？」

乙：「我幫人家辦事，抄了身份證號後人家離開了，然後打在電腦里提示這是不正確的身份證號，懷疑是不是抄錯了。現在還在想辦法聯繫人家……」

甲：「我看看哈……肯定是錯的。」

乙：「你怎麼也知道？」

甲：「十八位的號碼，真正記錄信息的是前十七位，最後一位是幫你檢查有沒有錯。」

乙：「還在想這為什麼如此靈光，幸虧電腦能提醒，要不然一個錯的號碼輸進去出了事就完蛋了。」

甲：「我們經常碰到的錯號無非就是兩類：一是該位的數字錯了，二是兩位或多位的數字順序錯了。」

乙：「您說說這兩種方法是怎麼解決的？」

甲：「您老人家筆算驗算時有沒有用過棄九法啊？」（可能有些人在這裡沒看懂，我在這裡添加了鏈接。）

乙：「用過哈，比如我算 2,017-1,949=68，將 2,017 各位相加得 10，減掉 9 為 1；1,949 去掉兩個 9 後各位相加得 5。」

甲：「那麼該怎麼算呢？」

乙：「1-5=-4，然後不在 0～8 之間的數要不斷加減 9，這樣變成 -4+9=5。結果的 68 兩位相加得 14，減掉 9 變 5，那麼 5=5 說明驗算正確。」

甲：「看來你也對這方面有些了解啊。可是有沒有想過，如果有幾位數字正好顛倒了順序呢？比如你把 2,017 寫成 2,107，用棄九法能檢查出來嗎？」

乙：「這……不好說吧，不過我還是想了解下。」

甲：「那麼我們可以給每位的數字乘上指定的不同的數字。比如三位數，百位乘 4、十位乘 2、個位乘 1，再相加。」

乙：「我看看啊：對於 123，算出來是 9；對於 321，算出來是 17……挺靈的！」

甲：「既然你知道了筆算驗算的棄九法，那麼也不難理解，校驗碼有點像棄九法里的那位數字，只是還得給每位乘上指定數字，然後最後除的數字可能不是 9，可能是其他的數字來取其餘數。」

乙：「那麼身份證號又是怎樣的呢？」

甲：「這樣，你現在有 18 位號碼，你假設不知道最後一位，把它記為 n。」

乙：「嗯，每位乘多少？」

甲：「從最後一位開始乘以 1，倒數第二位乘以 2，倒數第三位乘以 4……倒數第 n 位乘以 $2^{n-1}$ 。」

乙：「打住，最左邊的一位豈不是要乘以 $2^{17}=131,072$ 了？」

甲：「不急，到時候有簡化的演算法。把上述的數值乘好，相互間加好後，我們要除以 11 了。」

乙：「這個 11 有什麼講究？」

甲：「你先想想看，如果除以 10 以內的數會發生什麼後果？」

乙：「讓我想想……就拿 7 吧，比如我把其中一位的 1 錯填成 8 ，校驗碼 n 就不會發生變化，所以檢查不出錯誤。」

甲：「正確，想想那麼除以 10 呢？」

乙：「好像不容易想出來。」

甲：「我們這裡選擇了每位乘上 $2^{n-1}$ ，而 10=2×5。」

乙：「所以呢？」

甲：「先不看校驗碼所在位，其他位的數字經計算都是偶數了。」

乙：「那麼校驗碼也只能是偶數了？」

甲：「恭喜你答對了！那麼我們就選擇除以 11 吧，它與 2 的整數次冪無關，且會有 0～10 這 11 種結果，其中 10 用羅馬數字 X 來表示。」

乙：「怪不得這個 X 好神秘，還以為是特工的身份證號……」

甲：「說了這麼多了，我這裡有簡化演算法，本質是將 $2^{n-1}$ 對 11 取模，這裡的 $a_n$ 仍舊是從右往左的第 n 位：」

$7(a_{18}+a_8)+9(a_{17}+a_7)+10(a_{16}+a_6)+5(a_{15}+a_5)$

$+8(a_{14}+a_4)+4(a_{13}+a_3)+2(a_{12}+a_2)+a_{11}+6a_{10}+3a_{9}$

乙：「公式里的 $a_1$ 呢？」

甲：「這不就是你要算的 n 嗎？然後你要除以 11，得到 0～10 的餘數。」

乙：「讓我算算……算出來是 9，可是我身份證號最後一位數是 3 啊。」

甲：「還有一步，用 12 減該餘數，得到 2～12 的數字，最後 10→X、11→0，12→1。」

乙：「呼……終於算好了，果然如此。」

甲：「你那個錯誤的號給我，我看看問題在哪。」

乙：「不知道哪位錯了，不過最後一位我沒填錯。」

甲：「我看下……信息里的地址對的，生日對的……你是不是把倒數第二位的 6 填成 9 了？！」

乙無言。

附：身份證校驗碼簡明演算法

第一步：將前 17 位依次填入下面的方框，完成算式：

$7 imes□+9 imes□+10 imes□+5 imes□+8 imes□+4 imes□$

$+2 imes□+1 imes□+6 imes□+3 imes□$

$+7 imes□+9 imes□+10 imes□+5 imes□$

$+8 imes□+4 imes□+2 imes□$

（為便於觀察，算式分為四行：地址、出生年、生日、序列性別）

第二步：上式計算得出的數值，除以 11，取其餘數；

第三步：用 12 減去該餘數，如果結果在 2～10 之間，則該結果即為校驗碼（注意 10 用羅馬數字 X 表示）；如果結果為 11、12，則再減去 11，最終得到的 0、1 即為校驗碼。

沒什麼不方便，只是對強迫症不友好。

科學一點說，這是一個國際標準，基本考慮有兩個：

1. 十進位數字串的校驗碼不能小於10個（最少應為10），才能保證漢明距離大於等於2，才能排除單字錯誤。

2. 為交換位置也能被檢查出來。需要為每位配上不同的權重，這個數要與權重互質。

11是滿足兩個要求最小的數。

修訂：

根據評論修正位置和權重的表達。

漢明距離只是翻譯問題，就不改了。

如果模a，而a有小於10的質因子，那麼必定存在一個小於a的正整數b，使得存在兩個0到9之間的整數，在乘以b之後模a同餘。

於是11是滿足條件的最小的數。

話說校驗位改成兩位，不就沒這麼多爛事了嗎，模的數字還可以大點，比如19之類的，這樣每一位的乘數都可以互不相同，豈不美哉？

PS：我身份證結尾是X

不需要 mod 11。言之鑿鑿地說一定要和 10 互素之前難道不能自己先算算么？

不妨令 a_1,...,a_17 為身份證前 17 位；

使用權重 w = [7, 9, 1, 3, 7, 9, ..., 1, 3, 7]；

檢驗位 a_18 = sum_{i&<18} a_i w_i mod 10。

不難證明，這樣的校驗碼可以檢測

單個數字寫錯
相鄰兩位寫反（並不能，看 @王欽石 s-quark 的評論）
大概 90% 的其它錯誤

這個構造和證明應該不超過大學課程習題難度。

感謝邀請，具體為什麼我也不知道，不過一般編碼中的校驗碼要包含前面各個位的信息。如果是Mod 10，相當於僅重複最後1位。而Mod 11的話則包含了前面所有位的信息。

身份證除去最後的校驗位共17位，將最前面1位補為0，變為18位。轉為100進位，將是一個9位數。因為100 - 1 % 11 == 0，所以Mod 11的結果就相當於直接將這9個數加在一起再 Mod 11。因此11隱含了所有數字加和的信息。當然Mod 9也是可以滿足這個條件的。而Mod 8則只包括最後3位的信息。

身份證驗證演算法用的是mod11/2演算法。也就是2的i次冪的和第i位乘積的和對11取模。

2的冪對10取於只有2,4,8,6四種可能，取各個位數的乘積的和也必定是偶數，也就是說10個數字最多用到5個，20%的重複可能，這個顯然是過於浪費了。

發明這種校驗碼的人是天才，把它應用於身份證的人是蠢材！一個X帶來多大麻煩！

其他人已經說了十一對比起十有甚麼好處了。

但說信息論來說校驗的信息容量其實越大越好，為甚麼十一而不是更大，這可能是為了顯性說明這是校驗碼。

作為一個身份證號碼末位為X的人表示…上小學和初中有見過同學Y結尾…上高中見過有同學Z結尾…我中二的以為我是the chosen one（。

當初為什麼只能增加一位檢驗，如果兩位的話不是可以避免那個噁心的X？

外行有點好奇~~

...11是個質數

可以減少 Hash 碰撞

是這樣的么？

乃綿芥末介意那個X，就上書要求改成A嘛