|
发表于 2005-12-30 17:43:39
|
显示全部楼层
好像一般的人如果运气不是足够的好,很难看到 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。 |
|