mersenneforum.org ECM Stage 2 RAM
 Register FAQ Search Today's Posts Mark Forums Read

2018-12-05, 21:18   #34
GP2

Sep 2003

258910 Posts

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

2018-12-05, 21:29   #35
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2·2,819 Posts

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

Last fiddled with by VBCurtis on 2018-12-05 at 21:30

2018-12-05, 21:38   #36
PhilF

"6800 descendent"
Feb 2005

10111000112 Posts

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

2018-12-05, 21:58   #37
chalsall
If I May

"Chris Halsall"
Sep 2002

3×5×739 Posts

Quote:
 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?

2018-12-05, 22:42   #38
PhilF

"6800 descendent"
Feb 2005

739 Posts

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

Last fiddled with by PhilF on 2018-12-05 at 22:47

2018-12-05, 22:52   #39
Gordon

Nov 2008

509 Posts

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

2018-12-05, 22:53   #40
chalsall
If I May

"Chris Halsall"
Sep 2002

3·5·739 Posts

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

 2018-12-05, 23:03 #41 Gordon     Nov 2008 1111111012 Posts How much ram will it use? I am referring now to gmp-ecm. I'm currently working on M4007 with fairly high values for B1,B2 B1=32X1011 B2=12x1014 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
2018-12-05, 23:54   #42
PhilF

"6800 descendent"
Feb 2005

739 Posts

Quote:
 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?

Last fiddled with by PhilF on 2018-12-05 at 23:58

2018-12-06, 00:08   #43
chalsall
If I May

"Chris Halsall"
Sep 2002

3×5×739 Posts

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

2018-12-06, 02:07   #44
storm5510
Random Account

Aug 2009
Not U. + S.A.

9E516 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Prime95 Lone Mersenne Hunters 118 2022-07-04 18:19 G_A_FURTADO Information & Answers 1 2008-10-26 15:21 D. B. Staple Factoring 2 2007-12-14 00:21 jasong GMP-ECM 9 2007-10-25 22:32 Matthias C. Noc PrimeNet 5 2004-08-25 15:42

All times are UTC. The time now is 12:01.

Sat Feb 4 12:01:52 UTC 2023 up 170 days, 9:30, 1 user, load averages: 0.57, 0.65, 0.69