mersenneforum.org mprime and gmp-ecm miss P-1 factor.
 Register FAQ Search Today's Posts Mark Forums Read

 2008-01-31, 20:39 #1 geoff     Mar 2003 New Zealand 22058 Posts 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.
 2008-01-31, 20:58 #2 bsquared     "Ben" Feb 2007 65568 Posts 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
 2008-01-31, 21:25 #3 bsquared     "Ben" Feb 2007 1101011011102 Posts 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
 2008-01-31, 21:31 #4 geoff     Mar 2003 New Zealand 13×89 Posts Thanks Ben, I didn't know of such a limit.

 Similar Threads Thread Thread Starter Forum Replies Last Post kladner Software 14 2011-12-10 18:52 R.D. Silverman Cunningham Tables 2 2010-11-18 17:20 Sayfudeen PrimeNet 4 2008-03-27 14:50 R.D. Silverman NFSNET Discussion 0 2007-09-02 04:37 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