20200927, 19:51  #1 
Aug 2020
2·3·19 Posts 
Does ECM use the fact that factors of Mp has the form 2kp+1?
We know that TF and P1 make use of this information. If ECM doesn't use it at all, it would be very hard for me to imagine that there does not exist a better algorithm for finding Mersenne factors of the ECM range (25~70 digits).

20200927, 20:58  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2·5,323 Posts 
Quote:
"Better" depends greatly on the size of p. Trivial example: if p has 70 digits ... 

20200928, 15:30  #3  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
11645_{8} Posts 
Quote:
Is ECM practical on large exponents? Back at prime95 v19, the advent of support of exponents up to 79.3M, whatsnew.txt included the following: Code:
ECM can now run on large exponents. Once again, the slow GCD routine and high memory requirements might make this impractical for large exponents. 

20200928, 15:41  #4  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2996_{16} Posts 
Quote:
I answered your question as asked. To answer your latest question, I believe that GMP can handle gigabit integers. I do not know whether GMPECM can do so but would not be too surprised to learn that it can. Machine resources required would be nontrivial by most people's standards. Last fiddled with by xilman on 20200928 at 15:44 

20200928, 17:09  #5  
"Ben"
Feb 2007
110101001100_{2} Posts 
Quote:
Last fiddled with by bsquared on 20200928 at 17:10 Reason: tpyo 

20200928, 17:42  #6 
Random Account
Aug 2009
19·101 Posts 
It would be nice to be able to run ECM's on a GPU, entirely. Short of that, GMPECM does not appear to multithread. As far as I can tell, it only uses one CPU core, even if the utilization is spread across many cores. In my case, around 25% of capacity on each of four cores.
Someone here wrote a long time ago, "Running ECM's is like throwing darts at a dart board 25 yards away. You are lucky if you even hit the board." GMPECM uses "Sigma." Prime95 simply shows an "s." It is either a 15 or 16 digit decimal number. A seed value for a large random number generator. There has to be a better way... 
20200928, 17:45  #7 
"Curtis"
Feb 2005
Riverside, CA
1281_{16} Posts 

20200928, 19:04  #8  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
47·107 Posts 
Quote:
Quote:
Based on notes from old attempts to use GMPECM for P1 factoring of Mersenne primes, run times were prohibitively long for exponents of current or future interest, due to run time scaling p^2.03. Also it was what is now a 10 year old cpu. I used a build from http://gilchrist.ca/jeff/factoring/ which might not be current. My notes following are from mid 2018. See also attached pdf. 3E6 seconds for p~107 is about a month; extrapolation indicates many years at p~1G. Code:
gmpecm P1 run time scaling Parrot i3 cpu 2^p1 factored with B1~= p/6 to p/10 p run time 1999 15 msec Thu 07/19/2018 18:12:02.10 to Thu 07/19/2018 18:12:02.29 0.19 sec 9973 157 msec 4MB Thu 07/19/2018 18:19:47.68 to Thu 07/19/2018 18:19:49.01, 1.33 sec 99991 11654+9937+4852+421+18205 = 45069msec 187MB Thu 07/19/2018 18:23:17.28 to Thu 07/19/2018 18:28:38.00 = 5:10.72 (310.72 sec) 310.72 = c 99991^2.3658 c= 310.72/(99991^2.3658) = 4.6058e10 t=~ c p^2.3658 ram=~ k p^1.67; k=~ 8.35e7 check: 499979 39 minutes est. step 1 417428ms F 59686ms h 6552ms g_i 16927ms tmulgen 26613ms F(gi) 3885ms step 2 114052ms subtotal to here 645143ms timestamps say Thu 07/19/2018 23:43:26.06 to Fri 07/20/2018 2:30:11.11 = 2:46:45.05 (10,005.05 sec) 889MB extrapolated: 500K 13998 sec 2747 MB I may give it a try with more ram and a newer cpu someday. 

20200928, 22:35  #9 
Random Account
Aug 2009
19×101 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factors of numbers of special form  CRGreathouse  Abstract Algebra & Algebraic Number Theory  7  20190607 06:48 
Special Form of Mersenne and Fermat Number Factors  michael  Math  31  20150904 05:57 
Factors with special form  RedGolpe  Factoring  5  20111103 18:38 
A strange new (?) fact about Mersenne factors  ChriS  Math  14  20060412 17:36 
Factors of the Form 7 mod 8  JuanTutors  Data  3  20040329 02:31 