一种新的快速寻找大质数的方法——不是梅森质数

tsyxzh

首先来看几个简单的计算式：
3*3-2=7,
(4*4-2)/2=7,
5*5-2=23,
(6*6-2)/2=17,
7*7-2=47,
(8*8-2)/2=31,
9*9-2=79,
(12*12-2)/2=71,
13*13-2=167,
(14*14-2)/2=97,
15*15-2=223,
(16*16-2)/2=127,
计算值都是质数
10=7*1+3,10*10/2-1=49=7*7,
11=7*1+4,11*11-2=119=7*17,
17=7*2+3,17*17-2=287=7*41,
18=7*2+4,(18*18-2)/2=161=7*23
23=17*1+6,23*23-2=527=17*31
28=17*1+11,(28*28-2)/2=391=17*23
74=7*10+4=17*4+6,(74*74-2)/2=2737=7*17*23
都是合数，并且这些合数分解因数发现这些因数很有特点。
    当a为奇数时，b=a*a-2，当a为偶数时，b=(a*a-2)/2，暂时称a为b的根数。当b为合数时，b的根数a一定与某个比b小的质数b1及其根数a1满足条件a=b1*n+a1（n为自然数），而合数b则为质数b1的倍数，若b/b1仍为合数，则仍可以找到一个质数b2（b2=b1或b2≠b1）及其根数a2满足条件a=b2*n+a2，b/b1为b2的倍数，若b/b1/b2仍为合数，则仍可以找到一个类似的质数b3，直到b/b1/b2...为质数，以b'表示此质数，即b'=b/b1/b2...。此时，若b'>a，我们也把b'列入这种类型的质数，a列入b'的根数（之所以要把b'列入这种类型数，是因为它具有很多同样的性质）；若b'<a，则可以发现，质数b'也是这种类型的质数，并且满足a=b'*n+a'（a'为b'的一个根数）。
    我不知道是否有人对此类型的数做过研究并命名，为了下面的论述方便，姑且以我自己的姓氏为此类型数命名为熊式（英文xiongsh）数，其中的质数称为熊式质数，合数称为熊式合数。
    先对熊式数给一个准确的定义：对任意大于2的奇数a，a*a-2=b，对任意大于2的偶数a，a*a/2-1=b，如果b为质数，则称b为（原生）熊式质数，a为质数b的根数；如果b为合数，则称b为熊式合数，a为合数b的根数；合数b除以（一个或几个）熊式质数所得的大于a的质数b'若为原生熊式质数，我们也把a列入b'的根数，若质数b'不是原生熊式质数，则称为（次生）熊式质数，a为质数b'的根数。
    从上述计算式可以看出几个特点：
    1、熊式数中，质数的比例是比较高的（比普通奇数中质数的比例高）；
    2、熊式合数分解因素得到的质数全部是熊式质数；
    3、如果一个熊式数b的根数a与某个比a小的熊式质数b1及其某个根数a1满足a=b1*n+a1（n为自然数），则b一定是合数并且b一定可以被b1整除；相反如果一个熊式数b的根数a与所有比a小的熊式质数b'及其所有根数a'都不能满足a=b'*n+a'，则此熊式数为熊式质数；也就是说熊式质数b可以被b'整除的充分必要条件是b的某个根数a与b'及b'的某个根数a'满足条件a=b'*n+a'（n为自然数）；
    4、所有熊式质数都有且只有两个根数（尚未证明）。
    下面对以上特点进行证明。
    (1)一个熊式数b=a*a-2（a为奇数）或b=(a*a-2)/2=a*a/2-1（a为偶数），如果b可以被质数c整除，整除商为d，假定c<d，则有c<a<d。设n=int(a/c)，m=a-c*n（n为a整除c的商，m为整除余数），则a=c*n+m且m<c，m、n为自然数。a*a-2=(c*n+m)*(c*n+m)-2=c*c*n*n+2*c*n*m+m*m-2。其中c*c*n*n、2*c*n*m均能被c整除，若b能被c整除，则m*m-2也能被c整除。根据以上定义，若m为奇数且c=m*m-2或m为偶数且c=m*m/2-1，则m为质数c的原生根数；若m*m-2（或m*m/2-1）>c，则因为m<c所以(m*m-2)/c（或(m*m/2-1)/c）<c，m也为（原生或次生）熊式质数c的根数。特点2成立。
    (2)若熊式合数b的根数a与一个小于a的熊式质数b1及其根数a1满足a=b1*n+a1，则b=a*a-2=(b1*n+a1)-2=b1*b1*n*n+2*b1*n*a1+a1*a1-2。因为a1是b1的根数，所以a1*a1-2=b1或a1*a1-2可以被b1整除，又因为b1*b1*n*n、2*b1*n*a1均能被b1整除，所以熊式合数b可以被熊式质数b1整除。
    (3)由以上(1)、(2)证明了特点3成立。
    (4)因为熊式数只可能被熊式质数（或熊式质数的乘积）整除，而普通奇数有可能被任意质数整除，也就是相对于普通奇数，熊式数首先不包含熊式质数以外质数（如3、5、11、13等）的倍数（如9、15、21、25等），所以熊式数中质数的比例比普通奇数中质数的比例高，特点1成立。
    从上述可见，如果一个熊式数的根数是熊式质数7的倍数，则此熊式数就不能被7整除，如果一个熊式数的根数是熊式质数17的倍数，则此熊式数就不能被17整除，所以如果我们从最小的熊式质数往大挨个相乘的乘积作为根数去求一个更大的熊式数，则此熊式数除了不能被熊式质数以外的质数整除外，它还不能被这些小熊式质数整除，所以这样的熊式数中，质数的比例会更高，还有，因为1和2不是任何熊式质数的根数，所以，用小熊式质数的乘积加上1或2所得的数做根数求得的熊式数中，质数的比例同样高。暂时不妨称这样的质数为熊式大质数。不过，因为这样的熊式数一旦是合数，因为这个合数不能被求取其根数的质数整除，只能被更大的质数整除，所以由此求得的次生质数就相对比较小，故既然叫熊式大质数就不必包含这种相对较小的质数了。我已经求出了四个熊式大质数，(7*17)^2-2=14159、(7*17+2)^2-2=14639、(7*17*23)^2-2=7491167、(7*17*23+2)^2-2=7502119，由于计算机高级语言编程中整数位数的限制，用高级语言编程求更大的熊式大质数有点复杂，不过我还是会于近期求出几个更大的。

tsyxzh

我们再来看一下梅森质数。
    很多年前，有个叫梅森的人发现2^n-1类型的数中，质数的比例是比较高的，并且梅森列出了一些这样的质数（人们称这类质数为梅森质数），之后，很多人加入了寻找更大的质数的行列，找到的梅森质数越来越大，后来很多电脑加入了寻找更大的梅森质数行列，手工计算就望尘莫及。
    最近，我发现梅森数中，2^(2*n)-1型数（即2的偶数次方减去1）都是3的倍数，除了2^2-1=3是质数外，其余的都是合数，我不知道是不是已经有人发现了这一规律，更不知道在寻找梅森质数的程序中是否还在验证2^(2*n)-1型数，如果是，那么将程序改进一下就可以提高一倍的效率。
    在扣除了所有的3的倍数后，我们再来看梅森数，2^(2n-1)-1=2^2n/2-1=(2^n*2^n-2)/2（n为大于1的整数），这实际上就是一种特殊的熊式数，特殊在这种数的根数是2的整数次方，因此当这种数很大时，表达起来很简单。
    因为梅森数只是一种表达很方便的熊式数，其中质数的比例与普通熊式质数的比例差不多，而熊式大质数的比例是比普通熊式质数比例更高的质数，所以熊式大质数的比例比梅森质数高。怎么样？可以与梅森质数一决高下了吧？慢点！目前已知的梅森质数多大了？好象如果用十进制书写，用普通小号字书写也要写几公里长了吧？而用2^n-1格式书写，n不必书写很长吧？熊式大质数虽然比例比梅森质数大，但要表达一个比现有最大的梅森质数更大的熊式大质数，没有几个电脑屏幕是写不下来的，不会有人对这种数感兴趣吧？我想到了一个简单的表示方法，这种方法的前提是有一张熊式质数表，我们就用相乘得到根数的最后一个熊式质数前加一字母B来表示，这样根数b1*b2*b3...*bn求得的熊式数就表示成B(n)，b1*b2*b3...*bn+1求得的熊式数就表示成B1(n)，b1*b2*b3...*bn+2求得的熊式数就表示成B2(n)，这样除了理解困难一些外，书写起来就不比梅森数麻烦多少了，这样上面的四个熊式大质数就可以表示为B(17)=14159、B2(17)=14639、B(23)=7491167、B2(23)=7502119（注意：从上述理论上，B1(n)中的大质数比例应该和B(n)、B2(n)差不多的，但B1(17)和B1(23)均不是熊式大质数，不知后面的是否比例也低很多，如果是，可以干脆把这部分质数排除在熊式大质数之外）。还有一个折衷的方法是把2^n再乘几个小的熊式质数作为根数来求熊式质数，也就是在原来的梅森数基础上，在减去1之前，先乘几个小熊式质数的平方，这样折衷的数，书写不会太困难，质数比例又比梅森数高，是不是也比较完美？只是有一点，梅森数2^n-1在电脑之前就暗合了二进制，也许在电脑计算过程中会得益不少，比如梅森数在电脑中就是所有位都是1的二进制数，电脑中求2^n-1就是n个二进制1，而不必象熊式数那样需乘上半天，不知计算过程中的优越性是否会胜过十进制基础上的理论优势。

count

楼主有心了。写出了这样的文章。可是我要说梅森数搜索程序只检查 2^p-1，而p是素数的数。另外那程序用的是2进制, 计算2^p-1根本不费时间。还有, 检查2^p-1是否素数用的是卢卡斯-莱默测试(Lucas-Lehmer testing), 是比较简单的可靠素数检验法，详见 http://www.equn.com/gimps/math.htm , 再有借助了汇编写的FFT乘法，速度一流。

[ Last edited by count on 2005-8-19 at 23:08 ]

tsyxzh

谢谢count！说实话，我就是一时兴起，也没查多少资料，只了解到梅森质数是2^n-1型数，没想到先见到的那些文章均没多介绍。
看来我只是又做了一次井底之蛙而已。