mersenneforum.org Does ECM use the fact that factors of Mp has the form 2kp+1?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-27, 19:51 #1 Ensigm   Aug 2020 2·3·17 Posts Does ECM use the fact that factors of Mp has the form 2kp+1? We know that TF and P-1 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).
2020-09-27, 20:58   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×3×1,699 Posts

Quote:
 Originally Posted by Ensigm We know that TF and P-1 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).
No it does not.

"Better" depends greatly on the size of p. Trivial example: if p has 70 digits ...

2020-09-28, 15:30   #3
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

111478 Posts

Quote:
 Originally Posted by xilman No it does not. "Better" depends greatly on the size of p. Trivial example: if p has 70 digits ...
Does software for ECM for Mersenne primes with exponents greater than ~30 bits exist? If so what is it and where is it found? (Mprime/prime95 supports P-1 or ECM with B1 or B2 values >32 bits (4.29G) but is limited IIRC to p~1.1G or ~30+ bits on AVX512, and lower p on FMA3 or earlier hardware type.)
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.
https://www.mersenne.org/primenet/ shows ECM status only for p<40M.

2020-09-28, 15:41   #4
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×3×1,699 Posts

Quote:
 Originally Posted by kriesel Does software for ECM for Mersenne primes with exponents greater than ~30 bits exist? If so what is it and where is it found? (Mprime/prime95 supports P-1 or ECM with B1 or B2 values >32 bits (4.29G) but is limited IIRC to p~1.1G or ~30+ bits on AVX512, and lower p on FMA3 or earlier hardware type.) 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. https://www.mersenne.org/primenet/ shows ECM status only for p<40M.
You asked only about ECM, not about any specific implementation.

I answered your question as asked.

To answer your latest question, I believe that GMP can handle gigabit integers. I do not know whether GMP-ECM can do so but would not be too surprised to learn that it can. Machine resources required would be non-trivial by most people's standards.

Last fiddled with by xilman on 2020-09-28 at 15:44

2020-09-28, 17:09   #5
bsquared

"Ben"
Feb 2007

13×257 Posts

Quote:
 Originally Posted by kriesel Does software for ECM for Mersenne primes with exponents greater than ~30 bits exist? If so what is it and where is it found? (Mprime/prime95 supports P-1 or ECM with B1 or B2 values >32 bits (4.29G) but is limited IIRC to p~1.1G or ~30+ bits on AVX512, and lower p on FMA3 or earlier hardware type.) 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. https://www.mersenne.org/primenet/ shows ECM status only for p<40M.
I believe you and Xilman are talking about two different "p's". I believe he was referring to a notional prime factor of a candidate Mersenne number whereas you are talking about the exponent. For notional prime factors "p" of size 70 digits, it is indeed hard to imagine a method better than ECM as the constant factor "k" improvement enjoyed by trial division is dwarfed by the asymptotic complexity advantage of ECM for factors that large.

Last fiddled with by bsquared on 2020-09-28 at 17:10 Reason: tpyo

 2020-09-28, 17:42 #6 storm5510 Random Account     Aug 2009 U.S.A. 2·3·281 Posts It would be nice to be able to run ECM's on a GPU, entirely. Short of that, GMP-ECM does not appear to multi-thread. 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." GMP-ECM 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...
2020-09-28, 17:45   #7
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

27×5×7 Posts

Quote:
 Originally Posted by storm5510 There has to be a better way...
Why is that?

If you are referring to "better than one core at a time", run multiple copies. Or have ecm.py invoke multiple copies for you- it's quite a nice wrapper.

2020-09-28, 19:04   #8
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

7·673 Posts

Quote:
 Originally Posted by xilman You asked only about ECM, not about any specific implementation. I answered your question as asked.
Thank you for responding. Ensigm started the thread, not me. You replied to him in post 2. I don't recall posing any questions about ECM recently prior to post 3.
Quote:
 To answer your latest question, I believe that GMP can handle gigabit integers. I do not know whether GMP-ECM can do so but would not be too surprised to learn that it can. Machine resources required would be non-trivial by most people's standards.
I sometimes make factoring runs that take days or weeks each, and primality tests with good error checking in software and/or on ECC ram taking weeks or months, on systems with up to 128GB. Not sure what resources might be required for gmp or gmp-ecm on Mersenne exponents of interest to me. (Throughout the following I am using the GIMPS mersenne hunt convention p to refer to Mersenne exponent.)
Based on notes from old attempts to use GMP-ECM for P-1 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:
gmp-ecm P-1 run time scaling
Parrot i3 cpu
2^p-1 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.6058e-10
t=~ c p^2.3658

ram=~ k p^1.67; k=~ 8.35e-7

check:
499979 39 minutes est.
step 1 417428ms F 59686ms h 6552ms g_i 16927ms
tmulgen 26613ms F(g-i) 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
And Gilchrist's benchmark page shows P-1 considerably faster than ECM for the same input, admittedly much smaller integer and older software version. Gpu use (gpu-ecm) as far as I know is limited to ~4096 bits.
I may give it a try with more ram and a newer cpu someday.
Attached Files
 gmp-ecm scaling.pdf (16.2 KB, 18 views)

2020-09-28, 22:35   #9
storm5510
Random Account

Aug 2009
U.S.A.

168610 Posts

Quote:
 Originally Posted by VBCurtis If you are referring to "better than one core at a time", run multiple copies. Or have ecm.py invoke multiple copies for you- it's quite a nice wrapper.
This seems very doable. How many would depend on how much RAM each was allowed to use.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Abstract Algebra & Algebraic Number Theory 7 2019-06-07 06:48 michael Math 31 2015-09-04 05:57 RedGolpe Factoring 5 2011-11-03 18:38 ChriS Math 14 2006-04-12 17:36 JuanTutors Data 3 2004-03-29 02:31

All times are UTC. The time now is 09:37.

Fri Nov 27 09:37:50 UTC 2020 up 78 days, 6:48, 4 users, load averages: 1.39, 1.12, 1.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.