在计算机上实施素数判别的战略

　　在计算机上实施素数判别的战略

　　迄今为止，所有得到的素性判别法有简单明了的试除法，有赖宾等人的概率算法，有努卡斯到威廉斯的利用n±1，n2+1，n2±n+1的因子方法，还有艾德利曼—鲁梅利的最有效的近似多项式方法.这些方法各有利弊，它们各适用于适当的输入.上述第一种算法虽然很耗费

　　接了当，对较小的数n(最大不超过108)合适.第二种算法，用于作素性判别时，它可能出现差错，但出差错的可能性很小，因而可用它来确认哪些数最有可能是素数.努卡斯和威廉斯的n±1，n2+1，n2±n+1方法，对于20—50位的素数是有效的工具.艾德利曼—鲁梅利的方法是普遍的方法，它不依赖于待判别的数的特殊性，而且计算量是O((log2n)Clog2log2log2n)，故一般利用它来对50位以上的数来作素性判别.我们摘抄波门伦斯的一个表，它表明了三种方法的优劣.

　　另外，对有些特殊的数作素数判别时，用特殊的方法(如对2P-1，用勒默的方法)就可能很便利，就不必用艾德利曼—鲁梅利的方法.下面，我们指出在计算机上作素性判别的三大步骤.

　　对于一个待判定的数n(设n不具有我们了解的特殊形式)，实行下面三步：

　　(1)先用1到1000之间的素数(它们通常储存在计算机内)去试除.若n恰好有小的素因子，则不是素数，算法可停止;否则，进行下一步。

　　PrimeGrid 项目曾经被称为 Message@home，由立陶宛大学生 Rytis Slatkevičius 主持，项目仍处于开发测试阶段，注册、上传下载并不十分稳定。

　　PrimeGrid 项目试图通过因数分解来挑战 RSA 分解问题。RSA 是一套加密演算法，可以通过某种方式，把明文转换为密文。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数却十分困难。这个合数分解问题目前是尚未解决的一大难题。因此，要破解 RSA 密码也变得相当有难度。

　　RSA 公共密钥加密算法的核心是欧拉函数，其中的一个变量 n 的长度是控制该算法可靠性的重要因素。RSA-576 和 RSA-640 分别于 2003 年和 2005 年被攻破，位于其后的 RSA-704 目前尚未被攻破，攻破 RSA 将会对数学和密码学产生重要且积极的影响。而 PrimeGrid 目前正在尝试攻破 RSA-768。

　　另外，PrimeGrid 所使用的一些 BOINC 服务器组件是用编程语言 Perl 编写的，有别于别的项目。因此，该项目所承担的另外一样使命是，完善 Perl-BOINC 程序。