mersenneforum.org Are ECM curves with B1=50000 useful at all?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-07-30, 09:23 #1 keisentraut   Jul 2020 2×5 Posts Are ECM curves with B1=50000 useful at all? I recently did some ECM factoring (worktype 5, first factors of Mersenne numbers) on my laptop, mainly because those assignment do need less memory and finish fast (laptop does not run 24/7). Also, I like factors more than a LL-residue :) However, I'm doubtful that those B1=50000 assignments will be useful for numbers like M2655361: According to GMP-ECM, running around 250 of them gives us a good chance to find a factor of 25 digits or 83bits. We already know it has no factor below 76bits because of trial-factoring. P-1 was done to 2M and 50M, so the smallest factor who could be missed would be 2*2655361*50000001+1 which is also around 48bits. Most likely larger numbers would have been found with those bounds. If you already did n ECM curves with a given B1 bound, then the chance that the (n+1)th will find a factor is lower than for the very first curve, isn't it? Shouldn't we base the number of small ECM curves on the existing trial and P-1 factoring results? Or even start with B1=250000 (which will find the smaller ones after a few curves)?
 2020-07-30, 10:05 #2 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 5078 Posts The interesting and useful part is it's stage 2 with 5,000,000. In two days (e.g.), I found three factors to the following numbers in the 2M range with B1=50,000 (and B2=5,000,000): 2526553 2399933 2560849 That was lucky, of course. But I've been doing that for a long time now and found a lot of factors in that time. Last fiddled with by kruoli on 2020-07-30 at 10:05 Reason: Semantic error.
2020-07-30, 10:14   #3
axn

Jun 2003

22×11×107 Posts

Quote:
 Originally Posted by keisentraut If you already did n ECM curves with a given B1 bound, then the chance that the (n+1)th will find a factor is lower than for the very first curve, isn't it?
Correct. Technically each curve has the same chance of success, if there is a factor of appropriate size there to be found. But our apriori probability that there is such a factor gets lowered, every time there is an ECM failure.

Quote:
 Originally Posted by keisentraut Shouldn't we base the number of small ECM curves on the existing trial and P-1 factoring results? Or even start with B1=250000 (which will find the smaller ones after a few curves)?
Too much work. KISS.

250 curves at 50K is equivalent to 50 curves at 250K (in terms of effort).
Even if we jump directly to 250K, you're saving 50/600 or about 8%. Hardly worth the complications in adding more rules to the server.

Also, it is not like 50k ECM will magically stop at 25 digits. There is a small chance that it can find bigger factors (maybe as big as mid 30 digits).

2020-07-30, 10:15   #4
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

32710 Posts

Furthermore, welcome to the forum!

Quote:
 Originally Posted by keisentraut P-1 was done to 2M and 50M, so the smallest factor who could be missed would be 2*2655361*50000001+1 which is also around 48bits. Most likely larger numbers would have been found with those bounds.
To be a bit nitpicky, the smallest possible missed factor is $$f := 265537167455123 = 2 \cdot 2655361 \cdot k$$, where $$k = 50000201$$, because if $$k$$ would not be prime, it would have been found with a smaller bound. Also, $$f$$ has to be prime, otherwise it would have been found earlier.

Quote:
 Originally Posted by keisentraut If you already did n ECM curves with a given B1 bound, then the chance that the (n+1)th will find a factor is lower than for the very first curve, isn't it?
Unforunately, that's the Gamblerâ€™s Fallacy. I hate that, too, but you cannot ignore it.

2020-07-30, 10:16   #5
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

3×109 Posts

Quote:
 Originally Posted by axn But our apriori probability that there is such a factor gets lowered, every time there is an ECM failure.

2020-07-30, 10:49   #6
keisentraut

Jul 2020

10102 Posts

Thanks for your feedback. My assumption was that a single ECM curve is equally likely to find a factor like a P-1 run, but for P-1 computations are easier and you additionally gain extra "B1" because you can multiply the p of 2*k*p+1 Mersenne factors. Therefore, if we already did a P-1 test with B1=2000000, the chance that a new ECM curve with B1=50000 will find something is probably very unlikely. And that's what I have experienced, never found a factor with this work type so far (with P-1, quite a few). But at least it seems possible, given kruoli's examples!
Quote:
 Originally Posted by axn Even if we jump directly to 250K, you're saving 50/600 or about 8%. Hardly worth the complications in adding more rules to the server.
8% seems a lot and it shouldn't be hard to implement "start with higher B1" :) But yes, it is not saving much, an two stage ECM curve with B1=50000 for the 2M range takes a few minutes on my laptop.
Quote:
 Originally Posted by axn Also, it is not like 50k ECM will magically stop at 25 digits. There is a small chance that it can find bigger factors (maybe as big as mid 30 digits).
I know, but this is unlikely and we would find the factor with a larger curve, too. It's quite hard to optimize the ECM bounds given P-1/trial factorization bounds, even if you have a M.Sc. in math :)

Last fiddled with by keisentraut on 2020-07-30 at 10:56

 2020-07-30, 15:03 #7 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5·877 Posts You're welcome to manually set your ECM runs to 250k in that range; the server will convert them to a sort-of-equivalent number of 50k curves for the running tally. While it won't change your chances of success much, it will improve your chances of finding a larger (say, 28+ digit) factor by a bit. You might do, say, 50 curves at 50k, and then move up to 250k.
2020-07-30, 15:10   #8
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

104418 Posts

Quote:
 Originally Posted by kruoli Is it? Oops, sorry for my bad advice.
Consider the information you have before starting ECM versus the information you have after 1000 curves at B1=50k.

Before ECM, you have whatever TF data there is to tell you no factors below e..g 70 bits. There is the usual probability of a factor between 70 bits and 25 digits.

After 1000 curves of ECM, you have ruled out factors less than or equal to 25 digits with 1 - 1/e^4 probability or better (the 4th power comes from the curve count being 4 times the "expected" number of curves for 25 digit factors).

So, after 1000 curves you are quite sure there isn't a missed factor below 25 digits. But it's not like the 1000th curve is what convinced you- each curve you run without finding a factor decreases the chance there is a small factor to be found. It doesn't decrease the chances by much- that's why we run hundreds or thousands of curves at each level.

 2020-07-30, 15:22 #9 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 3·109 Posts Thanks for the clarification.

 Similar Threads Thread Thread Starter Forum Replies Last Post James Heinrich PrimeNet 3 2017-11-14 13:59 Walter Nissen Factoring 36 2014-02-16 00:20 SaneMur Riesel Prime Search 21 2011-11-02 20:10 WraithX Math 12 2010-09-29 09:34 henryzz GMP-ECM 3 2007-12-21 16:13

All times are UTC. The time now is 10:10.

Thu Oct 22 10:10:52 UTC 2020 up 42 days, 7:21, 0 users, load averages: 1.51, 1.25, 1.32

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.