mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2018-12-05, 21:18   #34
GP2
 
GP2's Avatar
 
Sep 2003

13×199 Posts
Default

Quote:
Originally Posted by PhilF View Post
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.
GP2 is offline   Reply With Quote
Old 2018-12-05, 21:29   #35
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7×13×61 Posts
Default

Quote:
Originally Posted by PhilF View Post
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
VBCurtis is offline   Reply With Quote
Old 2018-12-05, 21:38   #36
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

2·5·73 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
PhilF is offline   Reply With Quote
Old 2018-12-05, 21:58   #37
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

251568 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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?
chalsall is offline   Reply With Quote
Old 2018-12-05, 22:42   #38
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

2·5·73 Posts
Default

Quote:
Originally Posted by chalsall View Post
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
PhilF is offline   Reply With Quote
Old 2018-12-05, 22:52   #39
Gordon
 
Gordon's Avatar
 
Nov 2008

3×132 Posts
Default

Quote:
Originally Posted by lycorn View Post
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)
Gordon is offline   Reply With Quote
Old 2018-12-05, 22:53   #40
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

251568 Posts
Default

Quote:
Originally Posted by PhilF View Post
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)
chalsall is offline   Reply With Quote
Old 2018-12-05, 23:03   #41
Gordon
 
Gordon's Avatar
 
Nov 2008

1111110112 Posts
Default 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
Gordon is offline   Reply With Quote
Old 2018-12-05, 23:54   #42
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

2×5×73 Posts
Default

Quote:
Originally Posted by chalsall View Post
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
PhilF is offline   Reply With Quote
Old 2018-12-06, 00:08   #43
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·5,431 Posts
Default

Quote:
Originally Posted by PhilF View Post
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.
chalsall is offline   Reply With Quote
Old 2018-12-06, 02:07   #44
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
Not U. + S.A.

2,383 Posts
Default

Quote:
Originally Posted by chalsall View Post
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.
storm5510 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to use prime95 for stage 1 & GMP-ECM for stage 2 Prime95 Lone Mersenne Hunters 118 2022-07-04 18:19
Stage 1 G_A_FURTADO Information & Answers 1 2008-10-26 15:21
Stage 1 with mprime/prime95, stage 2 with GMP-ECM D. B. Staple Factoring 2 2007-12-14 00:21
Need help to run stage 1 and stage 2 separately jasong GMP-ECM 9 2007-10-25 22:32
Stage 1 and stage 2 tests missing Matthias C. Noc PrimeNet 5 2004-08-25 15:42

All times are UTC. The time now is 06:34.


Fri Dec 2 06:34:04 UTC 2022 up 106 days, 4:02, 0 users, load averages: 1.31, 1.00, 0.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔