[GIMPS]Stage 1 GCD 是个什么过程？

碧城仙

恕本人见识短浅，GCD 过程从来没看到过，Google 上倒是搜索到不少，要么是求助的，要是是说些不相干的东西的。

看下面的界面提示：
Starting stage 1 GCD - please be patient.
Stage 1 GCD complete. Time:264.521 sec.

帖图如下，从图片倒数第 6 行开始。

fwjmath

Stage1是Pollard p-1方法
这是一种概率型的素性检验方法
METHOD
Choose a number, N, you wish to factor
Choose a number, 1 < a < N, say a = 2
Choose a number, k, say k = 2
If gcd(a, N) is not 1, you have a factor. Otherwise...
Let t = a^k mod N
Let d = GCD( t-1, N )
Use division algorithm to see if d is a factor of N
YES? - You found a factor, you are done
NO? - Then...
Change a and/or k and go back to step 4

看看中间出现了gcd~~~
就是求最大公约数啦~~~

liqi

楼主请看帮助文件：

P-1 Factoring

The P-1 method is quite simple. First, pick a bound B1. P-1 will find the factor q as long as all factors of k are less than B1 (k is called B1-smooth).  Second, compute E - the product of all primes less than B1. Third, compute x = 3E*2*P. Finally, check the GCD (x-1, 2P-1) to see if a factor was found.

这是程序默认的执行步骤.

并且可以手动关闭跳过此步骤：

You can skip the GCD in stage 1 of P-1 factoring with this prime.ini setting:
Stage1GCD=0

碧城仙

呵呵，后来我又经历了 stage 1 GCD 阶段，现在进入 LL 阶段了。