素数的寻找（数论之素数测试与卡米歇尔数）

这是一系列关于数论的介绍性文章，目的在于推广数学知识，拓展读者的数学思维至于为什么用图文而不是视频？图文有三个优越性：一是图文数据量小，节省学习时间；二是有助于个人主动思考；三是文字里的关键字，可以方便读者查阅相关资料，今天小编就来聊一聊关于素数的寻找?接下来我们就一起去研究一下吧!

素数的寻找

这是一系列关于数论的介绍性文章，目的在于推广数学知识，拓展读者的数学思维。至于为什么用图文而不是视频？图文有三个优越性：一是图文数据量小，节省学习时间；二是有助于个人主动思考；三是文字里的关键字，可以方便读者查阅相关资料。

素数是整数的基本构件，并且有无穷多素数。小素数可以通过简单计算验证，如何判别一个大整数是不是素数，是个不容易的事情。

例如，对大素数

m = 113 736 947 625 310 405 231 177 973 028 344 375 862 964 001

与

n = 113 736 947 625 310 405 231 177 973 028 344 375 862 953 603,

利用尝试法，验证直至这个平方根的所有可能因数，工作量太大。将数自乘按非常大的数取模的非常高的幂次则不太困难，这些工作，对计算机更容易。

= 39 241 970 815 393 499 060 120 043 692 630 615 961 790 020(mod m)

费马小定理告诉我们，如果p是素数，则对每个整数a，因此，若 不与2(mod m)同余，m肯定不是素数。

我们已证明m不是素数，尽管不知道如何分解m。m是合数的证明确实没有提供任何能帮助我们寻求因数的线索。这告诉我们常常无需分解一个数就可得知它为合数。

考虑数

n = 113 736 947 625 310 405 231 177 973 028 344 375 862 953 603.

进行类似计算，求得

这里不能判断n是合数，利用费马小定理，我们可以判定一个数不是素数，却不能判断它是合数。

用更多的数，来验证n是不是素数，

我们仍不能用费马小定理得到n是素数的结论。但是，对a的99个不同值，暗示n是“可能”素数。

这是个很奇怪的断言，一个数怎样能成为“可能素数”呢？要么是素数要么不是素数。 假设我们将数n看作一种自然现象，并用试验科学家的精神研究n。通过选取数a的不同值并计算的值进行试验。如果单个试验产生甚至除a外的任何数，则得到n肯定是合数的结论。所以，有理由相信每次进行试验确实会得到我们收集n是素数的“证据”的数值a。

总结一下，通过观察a的n次幂不等于a的那些值，我们可在坚实的基础上进行这种推理。如果，我们说数a是n的证据。如果n是素数，则显然没有证据。

有一种奇怪的合数，它们不存在证据，比如561。1910年卡米歇尔注意到了这个现象，,所以用卡米歇尔来命名这种数。卡米歇尔数是这样的合数n，即对每个整数，都有

卡米歇尔数是可冒充素数的一种合数，因为它没有合数特征的证据。我们已看到561是卡米歇尔数，事实上它是最小的卡米歇尔数。下面是直到10000的所有卡米歇尔数的完全列表:561, 115, 1729, 2465, 2821, 6601, 8911。

卡米歇尔数有两个性质：

(A) 每个卡米歇尔数是奇数。

(B)每个卡米歇尔数是不同素数的乘积。

卡米歇尔数的两个性质(A)与(B)是有用的，有下述的卡米歇尔数判别法。

定理 (卡米歇尔数的考塞特判别法) 设n是合数，则n是卡米歇尔数当且仅当它是奇数，且整除n的每个素数p满足下述两个条件：

(1)不整除n.

(2)p-1整除n -1.

卡米歇尔数的存在，需要一个更好的检验合数的方法，目前有拉宾-米勒测试。

拉宾-米勒测试基于素数的以下性质。

定理 (素数的一个性质) 设p是奇素数，记

q是奇数.

设a是不被p整除的任何数，则下述两个条件之一成立：

(i)模p余1.

(ii) 数之一模p余-1.

转到开头素数的性质，我们得到被称为拉宾-米勒测试的合数试验。如果n是奇素数，且n没有前面的素数性质，则它必是合数；对a的许多不同值，如果n确实具有素数性质，则n可能是素数。

定理 (合数的拉宾一米勒测试) 设n是奇素数，记n-1=，q是奇数。对不被n整除的某个a，如果下述两个条件都成立，则n是合数。

(a)

(b) 对所有, .

对a的任何特别的选取，拉宾-米勒测试结论性地证明n是合数，也揭示出n可能是素数。n的合数性的拉宾一米勒证据是拉宾一米勒测试成功证明n是合数的数a。拉宾一米勒测试如此有用的理由归于下述事实。

如果n是奇合数，则1与n-1之间至少有75%的数可作为n的拉宾一米勒证据。

换句话说，每个合数有许多拉宾-米勒证据来说明它的合数性。所以，不存在拉宾-米勒测试的任何“卡米歇尔型数”。

举个例子，用a=2的拉宾-米勒测试应用到卡米歇尔数561。n-1 = 560 = ，计算

,，

第一个数既不是1，也不是-1，其他数也不是-1，所以2是561为合数的事实的拉宾-米勒证据。

,