Does ECM use the fact that factors of Mp has the form 2kp+1?

[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).

[xilman]

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 ...

[kriesel]

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:

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.

[xilman]

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:

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.

[bsquared]

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:

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.

[storm5510]

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...

[VBCurtis]

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.

[kriesel]

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.

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.

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.

[storm5510]

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.