ECM Stage 2 RAM

[GP2]

Originally Posted by PhilF

My question is: Is there any difference in the probability of finding a factor when performing ECM on a small Mersenne number vs. a larger one (assuming plenty of memory is available)?

The thing is, for small Mersenne numbers there has already been fairly deep ECM search done. It's easier to find factors for smaller Mersenne numbers, but many of the easy factors have already been found.

There are still new factors being found by ECM on a regular basis.

If you are interested in finding any new factors, including second and higher factors of exponents which already have at least one known factor, then it's probably a tossup whether you choose small or large Mersenne numbers.

If you're mostly interested in finding first factors of exponents without any known factors, then I think it is easier to find them for larger Mersenne numbers, simply because there's a lot of unexplored territory.

[VBCurtis]

Originally Posted by PhilF

My question is: Is there any difference in the probability of finding a factor when performing ECM on a small Mersenne number vs. a larger one (assuming plenty of memory is available)?

If you mean probability per curve run, given identical prior curves run on each number, there is no significant difference in probabilities by size of Mersenne input.

However, the probability of 1 ECM curve finding a factor for a number depends heavily on how much previous ECM has been run; if the ECM size you're considering has already been run thousands of times, the chances of the next one finding a factor are quite small compared to chances of the first ECM curve run on a number!

In terms of probability of finding a factor per day..... that's complicated. Smaller numbers have already been ECM'ed to small and medium bounds, so you'll need to use a pretty big ECM curve to find a factor; however, since the input is small, this curve might take a similar amount of time as smaller B1/B2 bounds on larger inputs. I think GP2 was commenting on this "factors per day" probability in his reply.

[PhilF]

Originally Posted by VBCurtis

If you mean probability per curve run, given identical prior curves run on each number, there is no significant difference in probabilities by size of Mersenne input.

That's really the answer I was looking for. I am just performing 1 curve per number and allowing the Primenet server to assign the work.

The numbers I'm being assigned are in the M12,000,000 and M19,000,000 range, with 4096MB of memory assigned (prime95 is actually using 3808MB in stage 2).

From what I can tell, all the numbers I'm getting have never had any curves run on them. So, based on your input, on numbers that have no prior curves run, the probability of any 1 curve finding a factor is not dependent on the length of the number being factored.

[chalsall]

Originally Posted by VBCurtis

However, the probability of 1 ECM curve finding a factor for a number depends heavily on how much previous ECM has been run; if the ECM size you're considering has already been run thousands of times, the chances of the next one finding a factor are quite small compared to chances of the first ECM curve run on a number

Incorrect.

Flip a fair coin a thousand times and it turns up heads each time. What is the chance it will turn up tails the next flip?

[PhilF]

Originally Posted by chalsall

Incorrect.

Flip a fair coin a thousand times and it turns up heads each time. What is the chance it will turn up tails the next flip?

I think we all know the next flip is not dependent on the previous flips. But I don't think that is an applicable analogy. Coins have just 2 sides, but the number of factors any given Mersenne number has is highly variable.

That is why I am running only 1 curve per candidate, and I assumed it is why the server assigns curves this way.

So if I hammer one number with 100 or more curves, and that number happens to have only a few very large, almost equal factors, the chances of finding them is almost zero. All those curves would be wasted.

However, if I run just one curve per number, some of them will be run on numbers with lots of factors, which decreases the chance of wasting curves on impossible candidates.

Of course I may be way off base here, because I admit the math is way above my head.

[Gordon]

Originally Posted by lycorn

It is indeed. I did some tests with GMP-ECM a while ago and, AFAIR, the useful limit was ~40K.

Not quite strictly true, here's one I found earlier

ECM found a factor in curve #25, stage #2
Sigma=3673943552503015, B1=1000000, B2=1000000000.
UID: nitro/haswell, M85027 has a factor: 113574028377227867558212550573836752813871 (ECM curve 25, B1=1000000, B2=1000000000)

[chalsall]

Originally Posted by PhilF

That is why I am running only 1 curve per candidate, and I assumed it is why the server assigns curves this way.

Similar thinking is why some people still play the lottery. Or, as some call it, a tax on those who are bad at the maths.... (no disrespect intended)

[Gordon]

I am referring now to gmp-ecm.

I'm currently working on M4007 with fairly high values for B1,B2

B1=32X10¹¹
B2=12x10¹⁴

I have 32gb in this system and gmp-ecm will try to use all that it can, there is a bug either in gmp-ecm or windows memory management.

When it gets to 16gig (not a typo) and tries to allocate another 4 gig chunk it fails with out of memory - even though 8 gig is still free...so I cap it at 14 gb for stage 2

[PhilF]

Originally Posted by chalsall

Similar thinking is why some people still play the lottery. Or, as some call it, a tax on those who are bad at the maths.... (no disrespect intended)

Well, the least you could do is point out the flaw in my logic.

I was under the impression that the reason the curves are split up into "levels" is due to the very reason I spelled out. Once a sufficient number of curves have been run at a specific level of a specific number, that level is considered done and the next level started. That is because the chance of finding a factor goes down as each curve in a level is run.

Am I wrong?

[chalsall]

Originally Posted by PhilF

Am I wrong?

Sorry. I was just being a bit flippant.

You are correct. The more searching done in a constrained space decreases the likelihood of success for each subsequent search attempt.

[storm5510]

Originally Posted by chalsall

The more searching done in a constrained space decreases the likelihood of success for each subsequent search attempt.

All of this is based on using random numbers. One could never be certain that all of the existing factors could be found at any level. I suppose the word "done" could be applied if many thousands of CPU's did many thousands of curves and found nothing new. Still, the possibility remains.