公民身份号码有可能是素数吗？

一句话结论

公民身份号码（仅考虑18位公民身份号码）有可能是素数，任意给定一个随机、有效的公民身份证号码，此号码为素数的概率理论上为2.20%，实际验证结果约为2.25%。

身份证号码的规律

身份证号的末位校验码算法最后一步模11是基于什么考虑？

这篇回答下面已经简要介绍了中华人民共和国公民身份号码的规定，这里不妨再详细展开介绍一下。

中华人民共和国国家标准《GB11643-1999 公民身份号码》第5节：号码的结构和表示形式中有如下规定：

5.1 号码的结构
公民身份号码是特征组合码，由十七位数字本体码和一位数字校验码组成。排列顺序从左至右依次为：六位数字地址码，八位数字出生日期码，三位数字顺序码和一位数字校验码。

这里我们仅考虑第二代身份证的身份号码，即上述18位身份号码。

5.1.1 地址码
表示编码对象常住户口所在县（市、旗、区）的行政区域代码，按GB/T 2260的规定执行。

这个GB/T 2260标准有点麻烦。

根据“标准下载库”的描述，中华人民共和国国家推荐标准《GB/T 2260 中华人民共和国行政区划代码》于1980年12月首次发布，1982年、1984年、1986年、1988年、1991年、1995年、1999年、2002年、2007年先后进行了九次修订。当前实施的版本为《GB/T 2260-2007/XG1-2016》，也就是2007年修订的版本，于2017年01月01日起正式实施。

GB/T2260-2007与GB/T2260-2002相比，主要变化表现在对应于行政区划变更的代码修订和区划名称变化，合计为：撤销数字码238个，新赋数字码255个；撤销字母码104个，新赋字母码103个；区划名称变化182处。这么看来，不同时间段还应该使用不同版本的国家推荐标准了。

这还不算完，打开中华人民共和国民政部网站，会发现民政部隔三差五就会调整一下地址码。2019年12月24日就发布了一次最新版本的《中华人民共和国县以上行政区划代码》。

幸好，我们可以找到很多已经用代码实现完毕的地址码库。https://github.com/cn/GB2260就是这样一个好用的地址码库，支持多种语言，童叟无欺！不过，为了方便起见，我直接到CSDN上找了一个看似能用的《2019年全国省市县行政区划编码表》：

2019年全国省市县行政区划编码表.xlsx-互联网文档类资源-CSDN下载

这个Excel文件里面总共包含了2884个地址码。

5.1.2 出生日期码
表示编码对象出生的年、月、日，按GB/T 7408的规定执行。年、月、日代码之间不用分隔符。
例：某人出生日期为1966年10月26日，其出生日期码为19661026。

这个比较简单。

5.1.3 顺序码
表示在同一地址码所标识的区域范围内，对同年、同月、同日出生的人编订的顺序号，顺序码的奇数分配给男性，偶数分配给女性。

这个看起来也比较…别忙，这里有一个很坑的点。

如果你是1999年之前出生的中华人民共和国公民，那你的户口本上最开始登记的身份证号码不是18位的，而是15位的，也就是少了出生日期码的前两位，以及最后一位校验码。少了出生日期码的前两位有一个很麻烦的问题：一个1899年出生的百岁老人和一个1999年出生的儿童，其出生日期码的前两位均是99，如果顺序码又一样，很可能这两个人都会具有相同的公民身份号码。为了解决这个问题，第一代身份证首次赋码时，将990~999留下备用，专门赋给百岁老人。不过，随着第二代身份证上公民身份号码升级为18位，上述问题已经不存在了，因此现在990~999已经不再作为百岁老人的备用顺序码。这方面具体可参考知友 @ls Shaw 的答案：

身份证号码有哪些秘密？

5.1.4 校验码
校验码采用ISO 7064:1983,MOD 11-2校验码系统。

这个解释起来有点复杂，我们直接上计算公式就好了。CSDN上的网友Stone.小小的太阳的文章《Java代码实现身份证合法性校验（全国所有地方）》中代码的注释很好地描述了校验码的计算和使用方法：

第十八位数字(校验码)的计算方法为：
1. 将前面的身份证号码17位数分别乘以不同的系数。从第一位到第十七位的系数分别为：7、9、10、5、8、4、2、1、6、3、7、9、10、5、8、4、2。
2. 将这17位数字和系数相乘的结果相加。
3. 用加出来和除以11，看余数是多少。
4. 余数只可能有0、1、2、3、4、5、6、7、8、9、10这11个数字，其分别对应的最后一位身份证的号码为1、0、X、9、8、7、6、5、4、3、2。

有了上述信息，理论上我们就可以生成所有可能的公民身份号码了。

素性检测

如何检测一个公民身份号码是否为素数呢？检测一个数是否为素数的算法称为”素性检测“。而当前比较易用的素性检测算法为Miller-Rabin素性检测法。Java编程语言BigInteger类中内置的素性检测算法即为Miller-Rabin素性检测法，实际上，BigInteger类中判断给定的BigInteger是否为素数的方法probablePrime中调用了一个私有方法passesMillerRabin，其注释为：

Returns true iff this BigInteger passes the specified number of Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS 186-2).

Miller-Rabin素性检测法并不是Miller和Rabin一起提出的。最开始，卡耐基梅隆大学的Gary Lee Miller首先提出的是一个基于广义黎曼猜想的确定性素性检测算法，但由于广义黎曼猜想并没有被证明，因此这一算法是否真的可靠尚不可知。随后，以色列耶路撒浪希伯来大学的Michael O. Rabin对此算法进行了修改，提出了不依赖于广义李曼猜想的随机素性检测算法。

Miller-Rabin素性检测法只能以非常非常大的概率判定一个数是否为素数，但不能100%判定。使用此算法时需要设置一个判定失败的概率，我们设置的概率为 $2^{-40}$ 。

如果想了解更多有关素性检测的知识，可以阅读Matrix67的文章：

http://www.matrix67.com/blog/archives/234

知友 @JoJo王颀的答案也非常值得一读：

用于加密的超大素数是怎么得到的？

初步估算结果

有了公民身份号码生成方法，也有了素性检测算法，理论上我们就可以生成所有可能的身份证号码，并把素数的公民身份号码挑出来了。不过在此之前，我们可以初步估计一下有多大比例的公民身份号码可能为素数。

知友 @xiaomm8341 已经指出：

根据素数定理，18位整数是素数的概率是： $\frac{1}{18 \ln(10)}=1/41.4465316739$
再加上末尾可能是X，所以需要乘以10/11，因此是素数的可能性平均是 $\frac{1}{18 \ln 10} \times \frac{10}{11} \approx 0.0219340647426 \approx 2.2\%$

实际上，素数定理描述了素数在自然数中分布的近似分布情况。素数定理指出，给出随着数字的增大，素数的密度逐渐降低。令 $\pi(x)$ 为不大于 $x$ 的素数个数，则有： $\pi(x) \approx \frac{x}{\ln x}$ 。

因此根据素数定理，给定任意一个长度为18位的整数（范围从0到999999999999999999），此整数为素数的概率近似为 $\frac{1}{\ln(10^{18})} = \frac{1}{18 \ln(10)}$ 。由于末尾为X的公民身份号码一定不是素数，故可得到一个初步的占比估计值 $2.2\%$ 。