mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-06-06, 02:12   #1
BigNumberGuy
 
May 2022

2110 Posts
Exclamation 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
BigNumberGuy is offline   Reply With Quote
Old 2022-06-06, 05:44   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

17×317 Posts
Default

Quote:
Originally Posted by BigNumberGuy View Post
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.
VBCurtis is online now   Reply With Quote
Old 2022-06-06, 06:11   #3
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

24A16 Posts
Default

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
bur is offline   Reply With Quote
Old 2022-06-06, 15:03   #4
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
Not U. + S.A.

22×571 Posts
Default

Quote:
Originally Posted by bur View 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...
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.
storm5510 is offline   Reply With Quote
Old 2022-06-06, 16:27   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

17×317 Posts
Default

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.
VBCurtis is online now   Reply With Quote
Old 2022-06-06, 19:14   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

667810 Posts
Default

Quote:
Originally Posted by bur View Post
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.
kriesel is offline   Reply With Quote
Old 2022-06-06, 20:22   #7
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·5,297 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.
chalsall is offline   Reply With Quote
Old 2022-06-06, 21:40   #8
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×32×7×53 Posts
Default

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
kriesel is offline   Reply With Quote
Old 2022-06-06, 21:49   #9
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

1059410 Posts
Default

Quote:
Originally Posted by kriesel View Post
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?
chalsall is offline   Reply With Quote
Old 2022-06-06, 22:50   #10
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·32·7·53 Posts
Default

(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
kriesel is offline   Reply With Quote
Old 2022-06-06, 23:09   #11
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2×5,297 Posts
Default

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

Been there. Done that. Multiple times.
chalsall is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
About M1277 BigNumberGuy Factoring 91 2022-08-02 03:59
Predict the number of digits from within the factor for M1277 sweety439 Cunningham Tables 7 2022-06-11 11:04
Python script for search for factors of M1277 using random k-intervals Viliam Furik Factoring 61 2020-10-23 11:52
M1277 - no factors below 2^65? DanielBamberger Data 17 2018-01-28 04:21
Hardware choice frustrations...is it just me? larrylogory Hardware 18 2008-07-03 09:46

All times are UTC. The time now is 02:32.


Fri Aug 19 02:32:51 UTC 2022 up 1 day, 1 min, 0 users, load averages: 1.22, 1.35, 1.40

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.

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