20201203, 10:46  #1 
Feb 2012
Paris, France
7×23 Posts 
Factor is found by GMPECM but not by GMPECM[GWNUM]
I wanted to switch from
GMPECM 7.0.4 [configured with GMP 6.1.2, enableasmredc] to GMPECM 7.0.4 [configured with GMP 6.1.2, GWNUM 29.8, enableasmredc] 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:
GMPECM 7.0.4 [configured with GMP 6.1.2, enableasmredc] [ECM] Tuned for x86_64/k8/params.h Input number is (103*10^2861)/(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^2861)/(3*43*47*9283691*60137568222544788641951))/42010916546178371843382678844466221253227 has 214 digits Peak memory usage: 4MB Code:
GMPECM 7.0.4 [configured with GMP 6.1.2, GWNUM 29.8, enableasmredc] [ECM] Tuned for x86_64/k8/params.h Due to incompatible licenses, this binary file must not be distributed. Input number is (103*10^2861)/(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 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. 
20201203, 16:47  #2 
P90 years forever!
Aug 2002
Yeehaw, FL
1110010110100_{2} Posts 
GWNUM only handles 53bit sigma values  8646756833320245055 was truncated.

20201204, 00:22  #3 
Mar 2019
90_{16} Posts 

20201204, 00:33  #4 
"Curtis"
Feb 2005
Riverside, CA
2^{2}·3·389 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 possiblesigma 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. 
20201204, 08:34  #5 
Feb 2012
Paris, France
10100001_{2} Posts 
Then when using a GMPECM linked with GWNUM the value of sigma
displayed is not the real one, I have to truncate it to a value < 2^{53} to deduce the real one? 
20201204, 15:41  #6 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{2}×11×167 Posts 
I am not familiar with the GMPECM code. The problem (truncation) may only occur when specifying a sigma on the command line.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factor found that should have been found by P1  tha  Data  65  20200805 21:11 
F12 factor found?  johnadam74  FermatSearch  16  20161103 12:10 
44digit factor found using ECM w/ B1=1e6 & B2=1e8  WVU Mersenneer  Factoring  8  20100424 17:01 
found this factor  tha  Factoring  4  20070618 19:56 
After a factor is found it keeps on going  jocelynl  Software  6  20040807 01:31 