mprime and gmp-ecm miss P-1 factor.
 

[My email to [email]ecm-dev@lists.fousse.info[/email] bounced]

According to PARI/GP, 13*2^20+1 is a factor of 6^(2^19)+1:
[code]
? (6^(2^19)+1)%(13*2^20+1)
0
[/code]

but P-1 with mprime version 24.14 and gmp-ecm versions 5.0.3 and 6.1.3
miss it with B1=100:
[code]
$ echo "6^(2^19)+1" | ecm -pm1 100
GMP-ECM 6.1.3 [powered by GMP 4.2.1] [P-1]
Input number is 6^(2^19)+1 (407976 digits)
Using B1=100, B2=55, polynomial Dickson(4), x0=1875995260
Step 1 took 11925ms
[/code]
[code]
$ cat worktodo.ini
Pminus1=1,6,524288,1,100,0

$ mprime -d
Mersenne number primality test program version 24.14
P-1 on 6^524288+1 with B1=100, B2=10000
Using generic reduction FFT length 160K
6^524288+1 stage 1 complete. 810 transforms. Time: 5.056 sec.
Stage 1 GCD complete. Time: 7.344 sec.
6^524288+1 stage 2 complete. 14826 transforms. Time: 96.657 sec.
Stage 2 GCD complete. Time: 6.843 sec.
[/code]

I have tested on Pentium 3, Pentium 4, and Core 2 Duo machines running
Debian Linux.


Regards,
Geoff.

I think gmp-ecm uses the common estimate that each prime Q less than the stage 1 bound only occurs in P-1 floor(log(B1)/log(Q)) times. Which with your B1 is 6 occurances. The factorization of 13*2^20, of course, has 20 occurances of the prime 2, so it won't be detected by P-1 with B1=100. You'd need a bound B1 of greater than 2^20 or 1048576.

- ben.

In gmp-ecm, you can use the option -go to input a known factor of P-1.

thus the following:
echo 6^524288 +1 | ecm -pm1 -v -go 2^20 100 55

finds the factor 13*2^20+1 because we've "preloaded" the stage 1 accumulator with the extra factors of 2.

I don't know if mprime has a similar option (never used it), but I'm sure the problem is the same.

Thanks Ben, I didn't know of such a limit.