mersenneforum.org Factor is found by GMP-ECM but not by GMP-ECM[GWNUM]
 Register FAQ Search Today's Posts Mark Forums Read

 2020-12-03, 10:46 #1 YuL     Feb 2012 Paris, France 2418 Posts Factor is found by GMP-ECM but not by GMP-ECM[GWNUM] I wanted to switch from GMP-ECM 7.0.4 [configured with GMP 6.1.2, --enable-asm-redc] to GMP-ECM 7.0.4 [configured with GMP 6.1.2, GWNUM 29.8, --enable-asm-redc] for my factoring work. So I was doing some testing and it appears that a factor found by the first one is not found by the second one: Code: GMP-ECM 7.0.4 [configured with GMP 6.1.2, --enable-asm-redc] [ECM] Tuned for x86_64/k8/params.h Input number is (103*10^286-1)/(3*43*47*9283691*60137568222544788641951) (255 digits) [Thu Dec 3 11:31:56 2020] Using MODMULN [mulredc:0, sqrredc:2] Using B1=6500000, B2=14271500890, polynomial Dickson(12), sigma=0:8646756833320245055 dF=16384, k=5, d=158340, d2=11, i0=31 Expected number of curves to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 178 1111 8108 67760 637802 6669522 7.6e+07 9.8e+08 1.3e+10 6.6e+11 Step 1 took 33016ms ********** Factor found in step 1: 42010916546178371843382678844466221253227 Found prime factor of 41 digits: 42010916546178371843382678844466221253227 Composite cofactor ((103*10^286-1)/(3*43*47*9283691*60137568222544788641951))/42010916546178371843382678844466221253227 has 214 digits Peak memory usage: 4MB Code: GMP-ECM 7.0.4 [configured with GMP 6.1.2, GWNUM 29.8, --enable-asm-redc] [ECM] Tuned for x86_64/k8/params.h Due to incompatible licenses, this binary file must not be distributed. Input number is (103*10^286-1)/(3*43*47*9283691*60137568222544788641951) (255 digits) Found number: 103*10^286 + -1 [Thu Dec 3 11:33:38 2020] Using MODMULN [mulredc:0, sqrredc:2] Using B1=6500000, B2=14271500890, polynomial Dickson(12), sigma=0:8646756833320245055 dF=16384, k=5, d=158340, d2=11, i0=31 Expected number of curves to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 178 1111 8108 67760 637802 6669522 7.6e+07 9.8e+08 1.3e+10 6.6e+11 Using gwnum_ecmStage1(103, 10, 286, -1, 6500000, 1) Step 1 took 27268ms Using 30 small primes for NTT Estimated memory usage: 81.07MB Initializing tables of differences for F took 52ms Computing roots of F took 720ms Building F from its roots took 552ms Computing 1/F took 300ms Initializing table of differences for G took 44ms Computing roots of G took 636ms Building G from its roots took 576ms Computing roots of G took 668ms Building G from its roots took 608ms Computing G * H took 168ms Reducing G * H mod F took 172ms Computing roots of G took 664ms Building G from its roots took 588ms Computing G * H took 164ms Reducing G * H mod F took 168ms Computing roots of G took 664ms Building G from its roots took 584ms Computing G * H took 160ms Reducing G * H mod F took 164ms Computing roots of G took 652ms Building G from its roots took 576ms Computing G * H took 152ms Reducing G * H mod F took 160ms Computing polyeval(F,G) took 1076ms Computing product of all F(g_i) took 8ms Step 2 took 10312ms Expected time to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 1.86h 11.60h 3.53d 29.47d 277.41d 7.95y 90.42y 1164y 15695y 790907y Peak memory usage: 139MB Lowering the value of B1, to say 3e6, exhibits the same behavior except that the factor is found in step 2 instead of step 1. Any thoughts? Note: I built the binaries myself, I patched the source code of ECM 7.0.4 to include rev3084 (which fixes the bug reported here) and that is the only change I made.
 2020-12-03, 16:47 #2 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 22×1,873 Posts GWNUM only handles 53-bit sigma values -- 8646756833320245055 was truncated.
2020-12-04, 00:22   #3
mathwiz

Mar 2019

7·23 Posts

Quote:
 Originally Posted by Prime95 GWNUM only handles 53-bit sigma values -- 8646756833320245055 was truncated.
Is the net result that GMP-ECM is less likely to find factors when linked with gwnum, and if so by how much? (what's the range of sigma values used?)

 2020-12-04, 00:33 #4 VBCurtis     "Curtis" Feb 2005 Riverside, CA 478410 Posts No, it just uses a smaller range of sigma. Each individual sigma has the same chance to find a factor, if one is to be found. Doesn't matter if the possible-sigma pool is 1 to 2^50 or 1 to 2^60. If the pool were 1 to 10^9, then running hundreds of thousands of curves would likely repeat some work- that's a waste, so the pool is much bigger than that. GWNUM has a higher chance to repeat a curve due to a smaller pool, but if you calculate the odds you'll see it's still very very unlikely.
 2020-12-04, 08:34 #5 YuL     Feb 2012 Paris, France 7×23 Posts Then when using a GMP-ECM linked with GWNUM the value of sigma displayed is not the real one, I have to truncate it to a value < 253 to deduce the real one?
 2020-12-04, 15:41 #6 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 22×1,873 Posts I am not familiar with the GMP-ECM code. The problem (truncation) may only occur when specifying a sigma on the command line.

 Similar Threads Thread Thread Starter Forum Replies Last Post tha Data 65 2020-08-05 21:11 johnadam74 FermatSearch 16 2016-11-03 12:10 WVU Mersenneer Factoring 8 2010-04-24 17:01 tha Factoring 4 2007-06-18 19:56 jocelynl Software 6 2004-08-07 01:31

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

Fri May 14 11:15:10 UTC 2021 up 36 days, 5:56, 0 users, load averages: 1.16, 1.61, 1.61