20200826, 19:59  #1 
Aug 2020
3×5×7 Posts 
How are the large factors more than 100 digits found?
Like this 128digit factor of M1171, or this 104digit factor of M1193. If the list https://members.loria.fr/PZimmermann/records/top50.html is up to date, then the largest factor found using ECM has just 83 digits. How are these factors with more than 100 digits found?

20200826, 20:05  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·3^{2}·509 Posts 
These are found by NFS method.
Mersenne numbers are a subset of the Cunningham project, where the exact method for factoring specific numbers is listed. 
20200826, 20:20  #3  
Aug 2020
1101001_{2} Posts 
Quote:
I see, thank you. For a given number, at what level shall we stop using ECM and switch to NFS? 

20200826, 20:37  #4  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3^{2}×509 Posts 
Quote:
Usually. people prefactor with TF, ECM etc until X% of the SNFScomplexity, or of GNFSsize. (where X varies between different opinions; search the forum, as well as SSW webpage and mathworld and similar). The problem in a nutshell is: 1) when factor is already known  you can easily look retrospectively and make a conclusion: "We would have needed N times _more_ time to keep ECMming and we would have found it ..or not" (and we could even arrive at paradoxical conslusion: "we would have saved so much time by not ECMming, skipping it altogether"); 2) we don't know the factor. We ecm up to the point when time to factor by NFS becomes less than the estimated time to get lucky with ECM (and factoring in probability that maybe it is out of reach of ECM). 

20200826, 20:38  #5  
"Curtis"
Feb 2005
Riverside, CA
2^{2}×1,123 Posts 
Quote:
For numbers where SNFS is faster, a rule of thumb is to ECM up to 0.22 * the difficulty of the number; e.g. SNFS300 would get ECM up to 66 digits (about 1.4 * T65). For numbers where GNFS is faster or SNFS is not possible, a rule of thumb is ECM to 0.31 * the number of digits; a GNFS200 would get 62 digits (2 * T60, or a T60 plus a T60 worth of T65sized curves). These rules of thumb are not super accurate; to be precise, one gives up on ECM when the marginal next set of ECM curves has less chance to factor the number than the fraction of expected NFSsolving time the set of curves takes. That calculation is tricky, to say the least, so the rules of thumb above exist; both my stated ratios are on the low side, many people do a bit more ECM than indicated here. 

20200826, 21:10  #6  
"Ben"
Feb 2007
3·5·223 Posts 
Quote:
If you are asking in general then Batalov and VBCurtis have good advice. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Nearly all Factors up to 2^69 found between 2.9G and 2.95G  Kalli Hofmann  Marin's Mersennearies  12  20191106 11:49 
Best Way to find large factors  mahnouman  Information & Answers  19  20130222 06:11 
No factors found  aketilander  PrimeNet  9  20110517 11:32 
5dpf, 5 digits from the end partial factors  dsouza123  Factoring  6  20040426 16:57 
More factors found with a new program  alpertron  ElevenSmooth  8  20031015 10:29 