mersenneforum.org GMP-ECM and ECM Frustrations [Was: About M1277]
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2022-06-06, 02:12 #1 BigNumberGuy   May 2022 258 Posts GMP-ECM and ECM Frustrations [Was: About M1277] Wow, I didn't expect this many responses. Thank you all for your time! EDIT: I am currently running ECM on this, how long would it take to finish t65? (or whatever its called) Last fiddled with by BigNumberGuy on 2022-06-06 at 02:18
2022-06-06, 05:44   #2
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

172×19 Posts

Quote:
 Originally Posted by BigNumberGuy EDIT: I am currently running ECM on this, how long would it take to finish t65? (or whatever its called)
How would we know? We don't know your hardware, what B1 bound you chose, etc. You can find out exactly how long by running a single curve with GMP-ECM and the -v flag. That -v gives you the curve counts required to get each T-level, and after the curve finishes it gives you an estimated time to complete a T-level. Try this with various B1 settings and you'll get a sense for which bounds make a T60 fastest, or a T65, or a T70, etc.

Since Ryan has already done a t70 or the majority of one, all ECM curves should be run at T75 level (or larger) which is around B1=7e9. It's not important what exact B1 you choose, if it's in that vicinity (so 6e9 or 8e9 are fine, but 1e9 is far too small and wasted effort). It would take a while to complete the T75 level, but we don't have to run the whole level to contribute! I've run about 800 curves with B1 around 7e9 myself, at about a CPU-day per curve on a very old Core2-Xeon (Dell 6100).

It's in your best interest to use the -maxmem option, unless you have 30+GB available for GMP-ECM.

 2022-06-06, 06:11 #3 bur     Aug 2020 79*6581e-4;3*2539e-3 601 Posts edit: Took to long pondering over the post... What do you mean by "running ECM"? Make sure you don't replicate all the lower B1 values, chances of finding a factor are miniscule once a lot of curves were run already. You'd need to start at B1=850M, preferrably higher. Try and see how long a curve takes... :) To get an idea about the probabilities, this page is very helpful. Enter the number of curves for the three highest B1 values that were run (smaller ones won't have any significant effect). You can use this table to see how many curves are usually run at each B1. And for M1277 there were likely run much more curves at each B1 value already. I also have a question about ECM. Is there exactly _one_ sigma value that will produce the factor or are there several ones? Is it guaranteed there is a "winning" sigma? If so, within which bounds? I guess not, because then ECM would be deterministic by testing all possible sigmas. And are the probabilities depending on the composite candidate? Are there composites for which more sigmas will produce a factor? Last fiddled with by bur on 2022-06-06 at 06:12
2022-06-06, 15:03   #4
storm5510
Random Account

Aug 2009
Not U. + S.A.

2×3×389 Posts

Quote:
 Originally Posted by bur ...What do you mean by "running ECM"? Make sure you don't replicate all the lower B1 values, chances of finding a factor are miniscule once a lot of curves were run already. You'd need to start at B1=850M, preferrably higher. Try and see how long a curve takes...
How about incrementally in ever increasing values? It would take some code writing to pair with GMP-ECM.

Quote:
 Examples: B1=100e6-99e6 B2=101e6 B1=101e6-100e6 B2=102e6 B1=102e6-101e6 B2=103e6
Individually, it may not take long to run these. In large groups might be a different story. Advantage: This would use a different sigma at each step creating a different curve.

 2022-06-06, 16:27 #5 VBCurtis     "Curtis" Feb 2005 Riverside, CA 10101011100112 Posts B1 is a single value, not a range. B2 is *much* larger than B1. Your example makes no sense. Really, I mean it- consider all curves at B1 below 2e9 useless for M1277.
2022-06-06, 19:14   #6
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

687610 Posts

Quote:
 Originally Posted by bur Is there exactly _one_ sigma value that will produce the factor or are there several ones? Is it guaranteed there is a "winning" sigma? If so, within which bounds? I guess not, because then ECM would be deterministic by testing all possible sigmas. And are the probabilities depending on the composite candidate? Are there composites for which more sigmas will produce a factor?
As I think I understand it, very thinly:
A sigma corresponds to a curve which corresponds to a set of points in a field. How many possible sigmas and curves are there? (Many; enough that it is expected that relatively few will be duplicated by selecting hundreds, to hundreds of thousands, of sigmas randomly for given bounds.) Are the curves guaranteed to not intersect at points corresponding to factors, so that factors are associated with unique sigmas? (Seems unlikely, given the large number of curves, and a guarantee of multiple intersections for each pair of curves; mn = 3x3 in Bezout's Law.) https://math.mit.edu/research/highsc...7-2%20Rhee.pdf
And a response would be very welcome from someone who understands it well.
If multiple sigmas will find the same factors for some small exponent, an existence proof by finding at least two sigmas yielding the same small factor(s) ought not be difficult. And it turns out to be easy to find such. (Probably by poorly chosen bounds for the small task, but prime95 enforces a minimum B1.)

As a fast experiment, M79, with two small factors 2687 and 202029703, which are also easily found with trial factoring.
Code:
prime95 v30.8b14 (minimum B1=50k)
M79
s                B1     B2           Factor found
4011674131322832 50000  2,000,000    542853811961 = 2687 x 202029703
4273748159069600 50000  2,000,000    2687
5375224073660968 50000  2,000,000    542853811961 = 2687 x 202029703
2914336596096327 50000  2,000,000    2687
7353150075666063 50000  2,000,000    202020703
6507411175456731 50000  2,000,000    2687
5176102690618798 50000  2,000,000    202020703
5758632202560064 50000  2,000,000    2687
7719672998703375 50000  2,000,000    202020703
Or M1009, ten curves run separately:
Code:
Sigma=17500281932646, B1=50000, B2=4000000. M1009 has a factor: 3454817
Sigma=17499395095926, B1=50000, B2=4000000. M1009 has a factor: 3454817
Sigma=908088127246459, B1=50000, B2=4000000. M1009 has a factor: 686066834105492663 = 3454817 x 198582684439
Sigma=2080153454287642, B1=50000, B2=4000000. M1009 has a factor: 3454817
Sigma=2080154903510001, B1=50000, B2=4000000. M1009 has a factor: 3454817
Sigma=2830004924066461, B1=50000, B2=4000000. M1009 has a factor: 686066834105492663
Sigma=3720592991825075, B1=50000, B2=4000000. M1009 has a factor: 198582684439
Sigma=3720595492188816, B1=50000, B2=4000000. M1009 has a factor: 686066834105492663
Sigma=4892655365568389, B1=50000, B2=4000000. M1009 has a factor: 3454817
Sigma=5642512694970646, B1=50000, B2=4000000. M1009 has a factor: 21624641697047
Testing "all possible sigmas" seems beyond impractical and unnecessary.

2022-06-06, 20:22   #7
chalsall
If I May

"Chris Halsall"
Sep 2002

23×3×5×89 Posts

Quote:
 Originally Posted by kriesel Testing "all possible sigmas" seems beyond impractical and unnecessary.
So, then, what is your conclusion?

What do you advise based on this research? What are the next experiments based on yours?

Perspiring minds want to know.

Ken et al... These are serious questions.

 2022-06-06, 21:40 #8 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 22·32·191 Posts Selecting M199 for a test run that would require stage 2 in P-1; 10 separate 1-curve B1=50000, B2=4000000 runs, succeeded in 7 of 10: Code: ECM found a factor in curve #1, stage #1 Sigma=5162481759413312, M199 has a factor: 164504919713 Cofactor is a probable prime! ECM found a factor in curve #1, stage #1 Sigma=5912327664438779, M199 has a factor: 164504919713 Cofactor is a probable prime! M199 completed 1 ECM curve ECM found a factor in curve #1, stage #2 Sigma=7974985130155996, M199 has a factor: 164504919713 ECM found a factor in curve #1, stage #2 Sigma=8865572054271244, M199 has a factor: 164504919713 ECM found a factor in curve #1, stage #1 Sigma=608224716041860, M199 has a factor: 164504919713 Cofactor is a probable prime! ECM found a factor in curve #1, stage #2 Sigma=1498813620767224, M199 has a factor: 164504919713 M199 completed 1 ECM curve M199 completed 1 ECM curve ECM found a factor in curve #1, stage #2 Sigma=4311317535291977, M199 has a factor: 164504919713 (This factor is only 37 bits so would have been found in the recommended 40-44 bits TF.) Or M257, B1=120000, B2=4000000, 10 separate curves run individually, of which two found the 49 bit factor that would not be found by recommended level TF (to 40-44 bits): Code: ECM found a factor in curve #1, stage #2 Sigma=5976369241598935, M257 has a factor: 535006138814359 M257 completed 1 ECM curve ECM found a factor in curve #1, stage #2 Sigma=8788874036099382, M257 has a factor: 535006138814359 M257 completed 1 ECM curve M257 completed 1 ECM curve M257 completed 1 ECM curve M257 completed 1 ECM curve M257 completed 1 ECM curve M257 completed 1 ECM curve M257 completed 1 ECM curve Last fiddled with by kriesel on 2022-06-06 at 21:41
2022-06-06, 21:49   #9
chalsall
If I May

"Chris Halsall"
Sep 2002

23·3·5·89 Posts

Quote:
 Originally Posted by kriesel Selecting M199 for a test run that would require stage 2 in P-1; 10 separate 1-curve B1=50000, B2=4000000 runs, succeeded in 7 of 10:
Um... Ken... This clarifies your argument exactly 0%.

Care to "wheel, and come again?

 2022-06-06, 22:50 #10 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 153348 Posts (Edit time slot expired on my previous post) A little experimentation with prime95 or whatever is handy can be enlightening. A modest laptop is sufficient. On M257, B1=120000, B2=4000000, the 10 separate curves run individually found the 49 bit factor that would not have been found with P-1 and the same bounds (requiring much bigger P-1 B2), but did not find the 80 bit factor that would have been found with P-1 and the same bounds as used here. A set of another 10 single-curve runs gave the factor found just once: ECM found a factor in curve #1, stage #2 Sigma=70969448337440, B1=120000, B2=4000000. M257 has a factor: 535006138814359 (ECM curve 1, B1=120000, B2=4000000) A quick look at prime95 v30.7b9 source code seems to confirm what the seed values listed above imply, that sigma ranges up to ~253. Max sigma seen in my samples ~ 8788874036099382 ~ 252.965 (nearly 1016) From ecm.cpp (// comments are mine present here only): Code:  double sigma; /* Sigma for the current curve */ Double offers 53 bits precision in the mantissa. Code: /* Choose curve with order divisible by 16 and choose a point (x/z) on said curve. */ do { uint32_t hi, lo; ecmdata.sigma = (rand () & 0x1F) * 65536.0 * 65536.0 * 65536.0; // highest five bits randomized ecmdata.sigma += (rand () & 0xFFFF) * 65536.0 * 65536.0; //next 16 bits if (CPU_FLAGS & CPU_RDTSC) rdtsc (&hi, &lo); ecmdata.sigma += lo ^ hi ^ ((unsigned long) rand () << 16); // the other 32 bits of 53? } while (ecmdata.sigma <= 5.0); if (w->curve > 5.0 && w->curve < 9007199254740992.0) { // 5 < curve <253 ecmdata.sigma = w->curve; w->curves_to_do = 1; } Last fiddled with by kriesel on 2022-06-06 at 22:52
2022-06-06, 23:09   #11
chalsall
If I May

"Chris Halsall"
Sep 2002

246708 Posts

Quote:
 Originally Posted by kriesel A little experimentation with prime95 or whatever is handy can be enlightening. A modest laptop is sufficient.
Indeed.

Been there. Done that. Multiple times.

 Similar Threads Thread Thread Starter Forum Replies Last Post BigNumberGuy Factoring 106 2022-09-12 12:20 sweety439 Cunningham Tables 7 2022-06-11 11:04 Viliam Furik Factoring 61 2020-10-23 11:52 DanielBamberger Data 17 2018-01-28 04:21 larrylogory Hardware 18 2008-07-03 09:46

All times are UTC. The time now is 04:14.

Thu Oct 6 04:14:04 UTC 2022 up 49 days, 1:42, 0 users, load averages: 1.73, 1.73, 1.59

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.

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