mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-09-27, 19:51   #1
Ensigm
 
Aug 2020

103 Posts
Default 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).
Ensigm is offline   Reply With Quote
Old 2020-09-27, 20:58   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

5×2,039 Posts
Default

Quote:
Originally Posted by Ensigm View Post
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 ...
xilman is offline   Reply With Quote
Old 2020-09-28, 15:30   #3
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

472510 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
kriesel is online now   Reply With Quote
Old 2020-09-28, 15:41   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

5×2,039 Posts
Default

Quote:
Originally Posted by kriesel View Post
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
xilman is offline   Reply With Quote
Old 2020-09-28, 17:09   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by kriesel View Post
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
bsquared is online now   Reply With Quote
Old 2020-09-28, 17:42   #6
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

32308 Posts
Default

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...
storm5510 is offline   Reply With Quote
Old 2020-09-28, 17:45   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×19×59 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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.
VBCurtis is online now   Reply With Quote
Old 2020-09-28, 19:04   #8
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

127516 Posts
Default

Quote:
Originally Posted by xilman View Post
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
File Type: pdf gmp-ecm scaling.pdf (16.2 KB, 18 views)
kriesel is online now   Reply With Quote
Old 2020-09-28, 22:35   #9
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

110100110002 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
storm5510 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factors of numbers of special form CRGreathouse Abstract Algebra & Algebraic Number Theory 7 2019-06-07 06:48
Special Form of Mersenne and Fermat Number Factors michael Math 31 2015-09-04 05:57
Factors with special form RedGolpe Factoring 5 2011-11-03 18:38
A strange new (?) fact about Mersenne factors ChriS Math 14 2006-04-12 17:36
Factors of the Form 7 mod 8 JuanTutors Data 3 2004-03-29 02:31

All times are UTC. The time now is 00:44.

Sat Nov 28 00:44:49 UTC 2020 up 78 days, 21:55, 3 users, load averages: 1.42, 1.47, 1.29

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.