搜索梅森素数的数学和计算机算法.doc

梅森素数的数学和计算机算法的一些知识本页面讨论用于高效地搜索梅森素数的数学和计算机算法的一些知识。由于相对于数学家,我更多地是计算机程序员,因此我将不深入到太多的数学细节中,而是设法提供链接代替。生成一个列表(Formingalist)很容易证明,如果2p-1是素数,则p也一定是素数。因此,搜索梅森素数的第一步就是生成一个用于测试的素数指数列表。试验分解因子(TrialFactoring)下一步是通过寻找小因子来排除一些指数。有一个非常高效的算法判断一个数是否能整除2p-1。例如,让我们看一下47是否能够整除223-1。把指数23转换成二进制数,我们得到10111。从1开始,重复以下步骤:平方,删除指数的最左边二进位,如果该位是1,则将平方后得到的值乘以2,然后计算其除以47后的余数。删除最左如果需要就  除以47平方     边二进位乘以2    的余数------------ ------- ------------- ------1*1=1   1 0111 1*2=2     22*2=4   0 111  no      44*4=16   1  11 16*2=32    3232*32=1024 1  1 1024*2=2048  2727*27=729 1    729*2=1458   1因此,223=1mod47。两边同时减1,223-1=0mod47。因此我们知道47是一个因子,从而223-1不是素数。可以证明梅森数有一个非常好的性质:2p-1的任何因子q必定是2kp+1的形式,并且q除以8的余数一定是1或者7。最后,一个高效的程序可以利用任何可能的因子q必须是素数这一事实。GIMpS程序的分解因子代码使用修正的厄拉托森斯(Eratosthenes)筛法,利用一个二进位表示一个可能的2kp+1形式的因子。这个筛排除能够被大约40,000以下的素数整除的任何可能的因子。同样,表示除以8的余数是3或者5的可能的因子的二进位被清除。这个过程排除大约百分之九十五的可能的因子。剩下的可能的因子使用上面描述的高效的算法进行测试。现在唯一的问题是要试验分解多少因子?答案取决于三个因素:分解因子的代价、发现一个因子的概率和素性测试的代价。我们使用以下公式:分解因子的代价<发现因子的概率*2*素性测试的代价也就是说,分解因子所花费的时间必须小于期望被节省的时间。如果能够发现一个因子,我们就能够避免进行首次素性测试和复查。根据以前分解因子的数据,我们知道发现一个2X到2X+1之间的因子的概率大约是1/X。本程序进行素性测试和分解因子所需的时间已经被计算出来。目前,本程序试图分解因子到:指数上限   分解因子到-----------  ------------3,960,000    2605,160,000    2616,515,000    2628,250,000    26313,380,000    26417,850,000    26521,590,000    26628,130,000    26735,100,000    26844,150,000    26957,020,000    27071,000,000    27179,300,000    272用p-1方法分解因子(p-1Factoring)还有另外一个方法可