Prime95图标处的提示

yulb

Prime95图标处的提示如下：
Prime95-2.87%P-1 stage 2
stage 2与别的贴子提到的三个阶段F D L是否有关系，如果没有关系，stage（进程）有多少段？

碧城仙

P-1 是一种分解因子的方法的名称！

目前大数分解最常见的有两种方法，P-1 factoring 和 ECM factoring 。

碧城仙

关于三个阶段的说明，请浏览本站 GIMPS 中文站：http://www.equn.com/gimps/math.htm

yulb

算到stage2（也就是算到2^69）结束后没有因子，比2^69大的还可能有因子吗，如果可能还有还应当继续计算啊，也就是还有stage3等步骤，如果没有应当是素数了，本机对该数的计算应当结束了，是不是？

nngs01

引用 yulb 在 2005-12-29 05:14 时的帖子:
算到stage2（也就是算到2^69）结束后没有因子，比2^69大的还可能有因子吗，如果可能还有还应当继续计算啊，也就是还有stage3等步骤，如果没有应当是素数了，本机对该数的计算应当结束了，是不是？

不是，你对GIMPS里分解因数方法的目的的理解有偏差。

彻底遍历一个数的所有可能因数来鉴别该数是否为素数的方法只对比较小的数可行。而GIMPS现在检查的数都太大了，不可能用这个方法来验证所有的素数。所以GIMPS主要用LL这个高效率的方法来验证素数。但即便是LL高效方法对目前的大指数而言也是很慢的（相信大家都有感觉）。所以GIMPS采用了分解因数（上面网友提到的方法）作为补充。这些补充方法就是只调查2^p-1很有限范围内的因数可能（而非遍历），尽量在对2^p-1进行LL计算前就能发现它的因子（GIMPS利用这个方法发现了非常多的合数，大大减轻了LL运算的任务量）。这些分解因数的任务是一种撞大运风格的任务，运算量可以调解，非常适合比较慢的机器来做，如pentium级别的，它们算一个典型的LL任务，大概至少一两年或更久，但它们通过分解一定范围因数的任务也能为GIMPS做可观的贡献（撞大运式的贡献）。当老机器对某个数撞大运失败了（没在调查范围内发现小因子），那GIMPS回收这个数留给快机器做LL检验。

上面说的针对F任务。GIMPS里还有一个P-1尝试（上面网友问的STAGE2之类的问题，算法与F任务不同），这也是个正式LL检验前试图先找小因子的努力。这个分解因数一般会发生在你的机器计算主LL检验前（这个过程喜欢内存越多越好），因为GIMPS的统计表明这个（用时大约几个小时到半天）撞大运还是值得的。很多人为了增加P-1找到因子的机会，甚至把内存加到了2G或更高。

[ Last edited by nngs01 on 2005-12-29 at 10:58 ]

yulb

已经基本知道了，stage2也是先试找小因子，等stage2结束后没找到因子，下一步提示的是stage3吗（正式LL检验），后面还有stage4没有？

碧城仙

好像一般的人如果运气不是足够的好，很难看到 stage 3，而 stage 4 不存在。关于 stage 3 的一点讨论可以参考 GIMPS 官方论坛上的讨论：http://mersenneforum.org/showthread.php?t=3362

在 dave_dm 的帖子中提到：

In a nutshell, stage 2 works by taking the residue s from the end of stage 1, computing s^t for various values of t, and then hoping that some s^t1 and s^t2 match modulo p. The point is that this can be done with far fewer operations than are needed to compute (for instance) s^(101 * 103 * ... * 44029) mod n. In practice this is done using polynomial arithmetic and huge lookup tables, it's no easy task to code up a fast implementation. Have a look at the gmp-ecm code if you want to see how complicated it can get!

On a purely conceptual level, recall:

Stage 1 finds a factor p if p-1 has all prime factors less than B1.
Stage 2 finds a factor p if p-1 has at most one prime factor in the range B1 <= x <= B2 and all the rest less then B1.

So the two most sensible suggestions for a third stage are:

a) Stage 3 finds a factor p if p-1 has at most two prime factors in the range B1 <= x <= B2 and all the rest less than B1.
b) Stage 3 finds a factor p if p-1 has at most one prime factor in the range B1 <= x <= B2, at most one prime factor in the range B2 <= x <= B3 and all the rest less than B1.

Unfortunately, nobody's thought of a good algorithm to implement either suggestion. The first in particular would speed up p-1 (and more importantly, ecm) hugely if it were possible!

I recommend looking at Brent's "Some integer factorization algorithms using elliptic curves" for an explanation of how p-1 stage 2 works and Montgomery's "An FFT Extension of the Elliptic Curve Method of Factorization" for details on how to write an efficient implementation.

按照他说的，阶段 3 是阶段 2 的后续阶段，但是必须阶段 2 之后的结果满足一定的条件才能有可能经历阶段 3。

Rojer

对数学方面不是很了解，现在清楚一点了