mprime and gmp-ecm miss P-1 factor.

[geoff]

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

According to PARI/GP, 13*2^20+1 is a factor of 6^(2^19)+1:

  ? (6^(2^19)+1)%(13*2^20+1)
  0

but P-1 with mprime version 24.14 and gmp-ecm versions 5.0.3 and 6.1.3
miss it with B1=100:

  $ 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

  $ 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.

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


Regards,
Geoff.

[bsquared]

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.

[bsquared]

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.

[geoff]

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