大数的素性检验在maple外文翻译资料

英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

---

大数的素性检验在maple

S.Y.YAN

数学系 英国约克大学

电子计算机系，白金汉郡布鲁内尔大学， 海威科姆

（1994 11月接收，1995 1月出版）

摘要：大数的素性检验在数学，计算机科学与密码学的许多领域都是非常重要的，近年来，很多现代的素性检测算法已纳入axiom和maple这样标准的软件计算机代数系统（科学）中。在本文中，我们讨论在maple V版本的大量素数测试。1994年发布新版maple，我们的计算经验表明，maple素性测试是否质数，基于一个强大，高效，可靠的伪素数试验和卢卡斯试验结合使用的设备。

关键词：可能的素数 质数检测 强伪素数试验 路卡斯试验 椭圆曲线测试

1.简介

大数素性测试在数学，计算机科学与密码学的许多领域都是非常重要的，比如公钥密码系统中，如果我能找到两个大素数和，每个有100个数字或更多，然后我们可以得到一个用200个数字或更多的复合数。该复合数可用于编码一个消息，即使是公开的（我们称为公共密钥）。没有了解的质因素不能被解码，当然，我们可以尝试使用一个现代化的整数分解方法，如因数的椭圆曲线法将得到其主要因子和因子，即使在超级计算机上完成这项工作，它也需要2000万年的工作，因此，它实际上无法解码消息。另一个很好的例子是寻找亲和数，在下面的代数方法会产生亲和数，如果我们能确保以下四个整数p，q，r，s

当

都是素数，然后是一对亲和数。因此，寻找亲和数通常为有关整数的素性测试。素数测试是一个最古老，以及开放的数学问题，追溯到古希腊大约2000年前，这个问题可以简单地描述为如下：

输入：（自然数和）因n此这个问题可以简单地描述为

输出：输出如

不幸的是，这不是一个简单的问题，来确定一个随机整数是否是素数，特别是当非常大。素数检测的一个高效算法，从复杂性的角度来看，必须运行在的步骤，对于一些固定的，但不幸，没有这样的确定性算法存在的随机整数，虽然米勒表明，假设改进未经证实的黎曼假设（ERH）的扩展，可以在的步骤里检测。最近，很多现代的Axion和maple 标准的素数测试算法被纳入计算机代数系统（CAS），在本文，我们将讨论大数素性测试在maple中，这里的maple，我们总是说maple v3版本。的是

我 2.强伪素数试验和卢卡斯试验素性测试

在本节中，我们介绍了一些基本概念和可能的素数，伪素数和伪素数试验的想法，这将用于整个纸张介绍，定理1（费马定理）如果是素数和，那么，大多数现代的素数测试算法在某种程度上依靠逆向（一个直接的推论）费马大定理。（费马定理，费马测试）让我们做一个正奇整数推论。如果和，那么是复合数。通过推论，如果存在一个，和，必须是合数，如果我们发现了一个数字会使得？我们能得出肯定是一个素数这个结论？答案很不幸，因为有时的确是一个素数，但有时不是，这导致了下面重要的可能素数和伪素数概念。

定义1如果，那么，我们称之（费马）为一个基数的可能素数，

能如果是合数，一个基数的可能素数叫做基数（费马）伪素数。

素数测试

举例，，因此，是一个基数为费马素数，但自从 是复合数,那么它是基数2的费马伪素数。进一步说，直接在费马测试改进强伪素数试验（常称为米勒拉宾试验，或者只是强检验）。我们描述下面算法的形式。

算法1（强伪素数试验）

[S1]设是奇数,依据的随机范围是，找到和与奇数，所以

[S2]计算，如果，那么是一个有可能的素数和输出是，然后停止。

[S3]去计算，那么是一个素数，和输出不是，然后停止，如果，那么是一个有可能素数和输出是然后停止。

[S4]重复步骤S3和被替换为。(注意顺序通常被称为米勒拉宾)

[S5]如果程序还没有终止，则是复合数，停止

定义2一个正整数，和是奇数，被称为强可能素数，如果通过上述的强伪素数试验（即，最后的在米勒拉宾序列项，第一次出现是在第一个任期内之前的）。如果是复合数，基数的一个强可能素数称为基数的强伪素数。

虽然很少的复合数可以通过强大的伪素数测试，但测试本身是不确定的，有概率，举例，复合数可以通过强伪素数试验，因为和米勒拉宾序列是2，所以是一个基数为的强伪素数。因此，我们不能得出这样的结论：通过强素数检测就是一个素数，我们还需要一些其他的测试。另一个试验是卢卡斯（伪素数）试验。注意到有一个特殊的卢卡斯测试，（通常称为卢卡斯测试），梅森素数，基于以下定理。

定理2。（梅森素数卢卡斯测试）设为奇素数。定义卢卡斯序列{}通过

的

如果只有, 是素数。

举例，假设我们希望测试是素数。我们首先计算卢卡斯序列{}对于：

en we 不幸是，

如果，那么是一个素数。我们在这里感兴趣的是一个更一般的卢卡斯测试，这是费马模拟卢卡斯序列的定理。

定理3（卢卡斯定理）让和是非零的整数和使，卢卡斯序列{}定义的参数使当和是俩个解，如果是一个奇素数，和,是一个雅可比符号，那么。

上面的定理可以直接用来构造素数检测，常被称为卢卡斯试验。

推论2。（卢卡斯定理的逆--卢卡斯检验）让我们做一个奇正整数。如果，是合数。

正如有费马可能的素数和费马伪素数，我们也有卢卡斯可能素数和卢卡斯伪素数的概念。

定义3一个奇正整数被称为一个卢卡斯可能素数，如果，如果是复合数，卢卡斯可能素数称为卢卡斯伪素数，

卢卡斯测试中最有趣的事情是如果我们选择的参数是。

1. 对于，是最小元素序列
2. 一个是最小的奇数超过,和

然后，第一个卡迈克尔数和其他几个基数为的费马伪素数永远不是卢卡斯伪素数，这导致了一个普遍的信息，一个强大的伪素数测试和卢卡斯测试组合可能是一个可靠的素性检测，至今，没有复合数被发现通过联合测试，因此，它是合理的推测来自于以下。

猜想1让是正整数并且,如果能通过一个强大的伪素数试验和卢卡斯试验组合，那么是质数。

波默朗斯等发出一个（总奖金620美元）挑战，举例一个复合数可以通过强大的伪素数试验、卢卡斯试验，或证明没有这样一个数字存在。在那一刻，无人去认领奖品；没有反例可以找到。素性测试设备和Maple V 3版本实际上是基于这个猜想，我们将在下一节讨论maple素性测试。

3.maple素性测试

maple是一个非常强大的计算机代数系统开发符号计算，在滑铁卢大学和科学计算研究所产生。它可以操作数学公式，数字理论，代数，几何，三角学，微积分和组合。在这一部分，我们只关心在maple素性测试设备的数字理论，以前的版本（即版本1和2）Maple V的素性测试设备是否素数只使用一个强大伪素数试验，所以一些伪质数和卡迈克尔数通过素数测试，在剑桥测试的下列数字。

素性测试

（第一，二个是费马伪素数和其他三个是卡迈克尔数字）

2152302898747 = 6763 bull; 10627. 29947

3474749660383 = 1303. 16927- 157543

10710604680091 = 3739. 18691 bull; 153259

4498414682539051 = 46411 bull; 232051 bull; 417691

6830509209595831 = 21319. 106591 bull; 3005839

发现他们可以通过Maple V版本是否质数测试，这是Maple V版本声明上述五个合成数是素数。但从maple 3版本开始，是否质数测试使用的是强伪素数试验和卢卡斯试验组合。我们测试了5个，用Maple V 3版，发现他们不能通过是否质数测试。也就是说，maple在这个时候宣布五个数字是复合数。正如我们所看到的，这些数字确实是复合数，所以maple V 3版提供了一个强大的和可靠的大数素性测试方法。

正如前面所提到的,素性测试是寻找亲和数的一个非常重要的操作。关于生成亲和数的一项研究代数方法的工作，我们利用Maple V 素数试验测试三个其他列表的整数。

列表y1：四个整数，

9288811670405087

145135534866431

313887523966328699903,

45556233678753109045286896851222527

p，q，r，s，这产生一个新的65位亲和数。

列表y2:68个q，r，s，204个整数，在101-122数字范围内它产生68个新的大型亲和数。

列表y3：在[ 1 ]中的2个大的520位数。

663228553696362109159972051763094684878515990025827353794913905891233290295650_

927164926978078060090008525720971052844194832159866585480713665440902566137427_

066765868827283517939906880431444760818325701672601612024082063487549161697774_

311098436355751715192728637914964348021736278380458303306889299215069309626816_

895201720064738466242877284877638913974106333092215777113364013087483467835695_

807181754057979471754499144424268957636699060565069202221342263517860285324742_

9237872442965593215267325943862952255228142339076351

632740275378922488701815325714175514794964816040594404799357848351264236526406_

845288532090020467602818361101121098304165256160155667579053088250671590322309_

057553824786443800578203216214872615909676099206945885060184879357274322644997_

254248956714784431538486182141543538783008629621566451550927419407740660304484_

945027709696773434687534485995266004134857036148105086354503584538997217621468_

327457083003403742747130571751051829100781214766777504855678715294348177033954_

7458147078975732794133237994324270311981965407027199

产生最大的1041位亲和数由霍格尔发现在西德。

在列表中210个所有数字发现在maple v版本3中是素数，这个测试大约只需半小时在平行硅图形R4D / 340S计算机约克大学计算机中心。注意，在1993年，我也测试了这210个数字在maple 2版本是素数，普渡大学布拉德利说，我在约克大学计算机中心的硅图形R4D/340S电脑里，已经证实和中所有的数字的确是素数，通过atkin和Morain 发展，使用一个确定的椭圆曲线测试算法ECPP（椭圆曲线素性证明），列表y3中作为俩个大于520的素数，事实上由法国的F. Morain利用一种新的一些程序ECPP版本完成。可我对获得的ECPP程序（即版本3.4.1，1991）并没有提供一个回溯设施，在这两个数字的运行过程中，大约20分钟后，数据会耗尽。我们已经在maple v 3版本中测试的最大的数是费马数F11中的564位素因子。

173462447179147555430258970864309778377421844723664084649347019061363579192879_

108857591038330408837177983810868451546421940712978306134189864280826014542758_

708589243873

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[30941]，资料为PDF文档或Word文档，PDF文档可免费转换为Word