作业帮就是sp2004的测试,多少单位的卢卡斯,这个卢卡斯是什么?
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/07 22:49:56
就是sp2004的测试,多少单位的卢卡斯,这个卢卡斯是什么?
就是sp2004的测试,多少单位的卢卡斯,这个卢卡斯是什么?
就是sp2004的测试,多少单位的卢卡斯,这个卢卡斯是什么?
卢卡斯-莱默测试(Lucas-Lehmer testing)
--------------------------------------------------------------------------------
卢卡斯-莱默素性测试是非常简单的：如果 P > 2,2P-1 是素数当且仅当 SP-2 = 0,其中,S0 = 4,SN = (SN-12 - 2) mod (2P-1).例如,证明 27 - 1 是素数的过程如下：
S0 = 4
S1 = (4 * 4 - 2) mod 127 = 14
S2 = (14 * 14 - 2) mod 127 = 67
S3 = (67 * 67 - 2) mod 127 = 42
S4 = (42 * 42 - 2) mod 127 = 111
S5 = (111 * 111 - 2) mod 127 = 0
为了高效地实现卢卡斯-莱默测试,我们必须寻找对巨大的数进行平方及对 2P-1 取余的快速方法.自二十世纪六十年代后期以来,对巨大的数进行平方的最快速的算法是：把巨大的数分裂成小片形成一个大数组,然后执行快速傅里叶变换(FFT),逐项平方,然后再进行快速傅里叶逆变换(IFFT).参见克努特的《计算机程序设计艺术》第二卷“乘法能有多快?”一节(译注:中文版第267页).1994年1月,由理查德·克兰多尔(Richard Crandall)和巴里·费金(Barry Fagin) 合著的题为“离散加权变换和大整数算术”的计算数学文章,引入了无理底数 FFT 的概念.这个改进使得计算平方的速度提高两倍以上,允许使用较小的 FFT,并且这一过程中自动执行了对 2P-1 取余步骤.虽然由于英特尔公司的奔腾处理器体系结构的原因,GIMPS 程序使用浮点 FFT,但彼得·蒙哥马利(Peter Montgomery)给出的一个纯整数加权变换的方法也能够被使用.
正如上一段所提到的,GIMPS 使用汇编语言编写的浮点 FFT 算法,充分利用流水线和高速缓存.因为浮点运算是不精确的,在每次迭代后浮点值舍入到整数.本来该有的整数结果和程序计算出来的浮点结果之间的差异叫做“卷折误差”.如果卷折误差超过 0.5 则舍入将产生不正确的结果 - 这意味着必须使用更大的 FFT.GIMPS 程序的错误检查确保最大卷折误差不超过 0.4.不幸地,这种错误检查的代价相当高,以致于不能在每次平方后都进行检查.存在另外一种代价很低的错误检查.FFT 平方的一个性质是：
(输入 FFT 值的和)2 = (输出 IFFT 值的和)
由于我们使用浮点数,我们必须将上式中的“等于”改为“约等于”.如果上式中两个值实质上不等,将给出一个在 readme.txt 文件中描述过的 SUMINP != SUMOUT 错误.如果输入 FFT 值的和是一个非法的浮点数(例如无穷大),将给出一个 ILLEGAL SUMOUT 错误.不幸地,这种错误检查无法发现我们将在下一节中描述的所有错误.
卢卡斯-莱默测试发现一个新的梅森素数的概率有多大?一个简单的估计是再次利用发现一个 2X 到 2X+1 之间的因子的概率大约是 1/X 的事实.例如,你已经使用试验分解因子证明 210000139-1 没有比 264 小的因子,那么它是素数的概率是:没有 65 二进位因子的概率 * 没有 66 二进位因子的概率 * ...* 没有 5000070 二进位因子的概率,即：
64 65 5000069
-- * -- * ...* -------
65 66 5000070
化简后得到：64 / 5000070,或者 1 / 78126.这个简单的估计不是很准确,它给出的公式是:(试验分解因子到多大的指数) / (指数/2).进一步的工作表明更精确公式是：(试验分解因子到多大的指数-1) / (指数 * 欧拉常数(0.577...)).在上例中,是 1 / 91623.这个更精确的公式是未经证明的.