mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-07-30, 09:23   #1
keisentraut
 
Jul 2020

2·5 Posts
Default 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)?
keisentraut is offline   Reply With Quote
Old 2020-07-30, 10:05   #2
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

32710 Posts
Default

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.
kruoli is online now   Reply With Quote
Old 2020-07-30, 10:14   #3
axn
 
axn's Avatar
 
Jun 2003

22·11·107 Posts
Default

Quote:
Originally Posted by keisentraut View Post
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 View Post
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).
axn is offline   Reply With Quote
Old 2020-07-30, 10:15   #4
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

1010001112 Posts
Default

Furthermore, welcome to the forum!

Quote:
Originally Posted by keisentraut View Post
  • 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 View Post
  • 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.
kruoli is online now   Reply With Quote
Old 2020-07-30, 10:16   #5
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

3·109 Posts
Default

Quote:
Originally Posted by axn View Post
But our apriori probability that there is such a factor gets lowered, every time there is an ECM failure.
Is it? Oops, sorry for my bad advice.
kruoli is online now   Reply With Quote
Old 2020-07-30, 10:49   #6
keisentraut
 
Jul 2020

2·5 Posts
Default

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 View Post
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 View Post
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
keisentraut is offline   Reply With Quote
Old 2020-07-30, 15:03   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5·877 Posts
Default

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.
VBCurtis is online now   Reply With Quote
Old 2020-07-30, 15:10   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5×877 Posts
Default

Quote:
Originally Posted by kruoli View Post
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.
VBCurtis is online now   Reply With Quote
Old 2020-07-30, 15:22   #9
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

3·109 Posts
Default

Thanks for the clarification.
kruoli is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM - why 3 curves? James Heinrich PrimeNet 3 2017-11-14 13:59
B1 and # curves for ECM Walter Nissen Factoring 36 2014-02-16 00:20
Adopting k= 4191; solved for up to n = 50000 SaneMur Riesel Prime Search 21 2011-11-02 20:10
Need help with elliptic curves... WraithX Math 12 2010-09-29 09:34
Curves needed henryzz GMP-ECM 3 2007-12-21 16:13

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

Thu Oct 22 09:25:00 UTC 2020 up 42 days, 6:35, 0 users, load averages: 1.51, 1.60, 1.53

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.