mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2008-01-31, 20:39   #1
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

22058 Posts
Default mprime and gmp-ecm miss P-1 factor.

[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:
Code:
  ? (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:
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:
  $ 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.
geoff is offline   Reply With Quote
Old 2008-01-31, 20:58   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

65568 Posts
Default

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.

Last fiddled with by bsquared on 2008-01-31 at 21:03 Reason: P,Q confusion
bsquared is offline   Reply With Quote
Old 2008-01-31, 21:25   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101011011102 Posts
Default

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.

Last fiddled with by bsquared on 2008-01-31 at 21:26
bsquared is offline   Reply With Quote
Old 2008-01-31, 21:31   #4
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Thanks Ben, I didn't know of such a limit.
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 bad factor, mprime kladner Software 14 2011-12-10 18:52
ECM Miss R.D. Silverman Cunningham Tables 2 2010-11-18 17:20
Wot did I Miss ??? Sayfudeen PrimeNet 4 2008-03-27 14:50
ECM (Near) Miss R.D. Silverman NFSNET Discussion 0 2007-09-02 04:37
Using mprime to factor with dual processors Hatori27 Factoring 4 2005-08-13 20:40

All times are UTC. The time now is 11:54.

Wed May 12 11:54:41 UTC 2021 up 34 days, 6:35, 0 users, load averages: 2.17, 1.72, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.