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

素数的寻找(数论之素数测试与卡米歇尔数)

素数的寻找

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

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

例如,对大素数

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为合数的事实的拉宾-米勒证据。

,