Are ECM curves with B1=50000 useful at all?

[keisentraut]

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)?

[kruoli]

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.

[axn]

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.

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

[kruoli]

Furthermore, welcome to the forum!

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.

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.

[kruoli]

Originally Posted by axn

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.

[keisentraut]

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!

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.

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 :)

[VBCurtis]

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]

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.

[kruoli]

Thanks for the clarification.