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

2022-06-07, 00:01   #12
storm5510
Random Account

Aug 2009
Not U. + S.A.

7·11·31 Posts

Quote:
 Originally Posted by VBCurtis 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.
PhilF used it sort of like a range when he was working on M1277. He ran stage 1 to 8e8 with Prime95, B1 and B2 matched, and used GmpEcmHook set to 1. His GMP-ECM line was like so:

Quote:
 echo "2^1277-1" | ecm -resume saved.txt 8e8-8e8
He speicified no B2 which allowed GMP-ECM to pick a B2 it devised was proper. His 8e8-8e8 'appears' to fix B1 at that level, and no lower.

My example was simply that, just an example. If I had used "e9" instead of "e6". It should not be hard to devise an experiment to see what works and what does not using a small exponent with a known small factor.

2022-06-07, 00:23   #13
storm5510
Random Account

Aug 2009
Not U. + S.A.

7×11×31 Posts

This did not take long to devise. Somebody tell me why this works when, in theory, it should not...

Quote:
 2022-06-06 20:04:48.803 Mon 06/06/2022 20:04:48.76 2022-06-06 20:04:48.803 2022-06-06 20:04:48.803 GMP-ECM 7.0.4-dev [configured with MPIR 2.7.2, --enable-openmp] [ECM] 2022-06-06 20:04:48.803 Tuned for x86_64/corei7/params.h 2022-06-06 20:04:48.803 Input number is 2^7363-1 (2217 digits) 2022-06-06 20:04:48.819 Using special division for factor of 2^7363-1 2022-06-06 20:04:48.819 Using B1=50000000-49000000, B2=0, polynomial x^1, sigma=0:14554909564759156736 2022-06-06 20:04:48.819 dF=0, k=0, d=13811920, d2=0, i0=0 2022-06-06 20:04:48.819 Expected number of curves to find a factor of n digits: 2022-06-06 20:04:48.819 35 40 45 50 55 60 65 70 75 80 2022-06-06 20:04:48.819 485 2769 17674 124445 956543 7963244 7.1e+07 6.7e+08 1.5e+10 Inf 2022-06-06 20:04:48.819 Step 1 took 0ms 2022-06-06 20:04:48.866 ********** Factor found in step 1: 223 2022-06-06 20:04:48.881 Found prime factor of 3 digits: 223 2022-06-06 20:04:48.881 Composite cofactor (2^7363-1)/223 has 2215 digits 2022-06-06 20:04:48.881 Peak memory usage: 4MB
The above uses no B2. The below does.

Quote:
 2022-06-06 20:17:59.299 GMP-ECM 7.0.4-dev [configured with MPIR 2.7.2, --enable-openmp] [ECM] 2022-06-06 20:17:59.299 Tuned for x86_64/corei7/params.h 2022-06-06 20:17:59.299 Input number is 2^7363-1 (2217 digits) 2022-06-06 20:17:59.299 Using special division for factor of 2^7363-1 2022-06-06 20:17:59.299 Using B1=50000000-49000000, B2=51000000, polynomial x^1, sigma=0:3505640519161039860 2022-06-06 20:17:59.299 dF=360, k=2, d=3150, d2=11, i0=15545 2022-06-06 20:17:59.299 Expected number of curves to find a factor of n digits: 2022-06-06 20:17:59.299 35 40 45 50 55 60 65 70 75 80 2022-06-06 20:17:59.299 453 2426 16018 111016 779638 6882350 5.5e+07 5.6e+08 8.6e+09 2.6e+11 2022-06-06 20:17:59.299 Step 1 took 0ms 2022-06-06 20:17:59.299 Estimated memory usage: 15.23MB 2022-06-06 20:17:59.299 Initializing tables of differences for F took 0ms 2022-06-06 20:17:59.315 Computing roots of F took 31ms 2022-06-06 20:17:59.384 Building F from its roots took 78ms 2022-06-06 20:17:59.446 Computing 1/F took 62ms 2022-06-06 20:17:59.446 Found factor while computing fd[] 2022-06-06 20:17:59.565 ********** Factor found in step 2: 223 2022-06-06 20:17:59.565 Found prime factor of 3 digits: 223 2022-06-06 20:17:59.565 Composite cofactor (2^7363-1)/223 has 2215 digits 2022-06-06 20:17:59.567 Peak memory usage: 19MB

 2022-06-07, 01:00 #14 BigNumberGuy   May 2022 1516 Posts Can somebody please tell me why tf does my computer say "segmentation fault" whenever I only set B1 and it completes the first curve? I am so confused (I'm using B1=110000000) (Does it have anything to do with my RAM? I have 8 GB) EDIT: I know that using low B1 is useless, but still, why does my computer kill the process when it goes to stage 2? (MacOS) Last fiddled with by BigNumberGuy on 2022-06-07 at 01:23
 2022-06-07, 01:16 #15 BigNumberGuy   May 2022 3×7 Posts Also this "GMP-ECM" thing you guys are talking about, how do you use it? (I'm not an expert please don't judge)
2022-06-07, 01:57   #16
charybdis

Apr 2020

11011010112 Posts

Quote:
 Originally Posted by VBCurtis 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.
Quote:
 Originally Posted by storm5510 This did not take long to devise. Somebody tell me why this works when, in theory, it should not... Code: ...Using B1=50000000-49000000, B2=0...
Well, technically B1 can be a range. usually we multiply a point on an elliptic curve by the product of all primes below B1, but if you've already multiplied by the primes below some bound and saved the residue, then you can extend to a higher B1 by only multiplying by the primes between your old bound and your new bound. This can be accomplished with the -save and -resume options in GMP-ECM.

One would have to be an idiot to want to only multiply by large primes, as that drastically reduces the chance that the group order divides our product of primes. GMP-ECM therefore has inbuilt idiot-proofing and will refuse to run if you specify B1 as a range without a saved residue. Of course no-one would ever be so perverse as to specify a backwards range for B1... or so I'd have thought until storm5510 just did it. The authors of GMP-ECM apparently didn't foresee this possibility - frankly, I don't blame them - and the result is that it runs a curve with no stage 1 at all. You'll see the exact same results if you use B1=0.

2022-06-07, 10:58   #17
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

100110011102 Posts

Quote:
 Originally Posted by storm5510 … like a range …
There is at least some truth behind this. Yes, you will set a range for B1 if you resume a save file. In this case, you will set it to {B1 it was run at}-{B1 it was run at}. This enables GMP-ECM to select a good B2, since it would not know the B1 otherwise.

A second possibility to use ranges is to split stage 2. If you have completed stage 1 and saved the residue, you could select a sensible B2, choose in how many parts you want to split it, and would run GMP-ECM while resuming the stage 1 file like this (step size is (selected B2 - original B1) / step count):
run B1={original B1}-{original B1}, B2={original B1}-{original B1 + step size}
run B1={original B1}-{original B1}, B2={original B1 + step size}-{original B1 + 2 * step size}
run B1={original B1}-{original B1}, B2={original B1 + 2 * step size}-{original B1 + 3 * step size}
run B1={original B1}-{original B1}, B2={original B1 + 3 * step size}-{original B1 + 4 * step size}
$$\hspace{20em}$$⋮
run B1={original B1}-{original B1}, B2={original B1 + (step count - 2) * step size}-{original B1 + (step count - 1) * step size}
run B1={original B1}-{original B1}, B2={original B1 + (step count - 1) * step size}-{selected B2}

2022-06-07, 11:09   #18
bur

Aug 2020
79*6581e-4;3*2539e-3

601 Posts

edit: Sorry, I thought my edit was fast enough. It wasn't, so retina's reply is to the original version.

Quote:
 Originally Posted by kriesel 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.
Thinking about the group order, I think a factor does not "have a sigma". It is just that each sigma/factor combination produces a unique group order. And the factors of the group order have to be B1/B2 smooth.

The winning sigma just happened to have factors that math the current B1/B2 settings.

And the probability to find a factor with a given B1/B2 just corresponds to the probability that a sigma will be found that is B1/B2 smooth.

The question that remains, is there an upper bound for the group order of a sigma/factor combination? If so, then there'd be a B1 that would be guarenteed to find that factor, i.e. B1 = (max_GroupOrder)^1/2.

Last fiddled with by bur on 2022-06-07 at 11:28 Reason: complete rewriting

2022-06-07, 11:17   #19
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

664110 Posts

Quote:
 Originally Posted by bur What I'm trying to get at, if it's a finite amount of sigmas and there is always a sigma for a factor, then in principle ECM would be deterministic.
It's deterministic in the same way TF is deterministic. That is, if you have infinite computing power available then you will find all factors. In practice you might have some difficulty obtaining that amount of computing power.

Plus the software we currently have only uses a small subset of all possible sigmas. You only get 53 bits to choose from. So that will hinder your ability to find factors even if you could run through all 2^53 available values.

Last fiddled with by retina on 2022-06-07 at 11:18

2022-06-07, 14:33   #20
charybdis

Apr 2020

53×7 Posts

Quote:
 Originally Posted by bur The question that remains, is there an upper bound for the group order of a sigma/factor combination? If so, then there'd be a B1 that would be guarenteed to find that factor, i.e. B1 = (max_GroupOrder)^1/2.
Yes: for a prime p, the group order is always within 2sqrt(p) of p+1, by Hasse's theorem. Of course the resulting B1/B2 that are guaranteed to find the factor are absurdly high for factors that we care about. As retina says, at that point you might as well be running TF.

2022-06-07, 14:36   #21
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·7·127 Posts

Quote:
 Originally Posted by bur Thinking about the group order, I think a factor does not "have a sigma". It is just that each sigma/factor combination produces a unique group order. And the factors of the group order have to be B1/B2 smooth. The winning sigma just happened to have factors that math the current B1/B2 settings.
In a small number of test cases, I saw 2 of 10, 7 of 10, or even 10 of 10 sigmas tried find a specific factor. Which seems to me very strong support for winning sigmas not being unique for a factor. Also, like for P-1, sometimes ECM returns a product of prime factors; one ECM sigma finding multiple factors.

I guess you meant match there not math. (I don't think you mean the sigma value's factors matter. Among the least smooth winning sigmas in this post are 7974 985130 155996 = 22 × 1993 746282 538999, and 5912 327664 438779 = 47 × 125 794205 626357; in a previous post, at least sigma value 4892 655365 568389 is prime.)
Perhaps you meant something like, the winning sigma generates a curve containing points corresponding to some factors of the number of interest, that are findable with the current B1 and B2 settings.

Quote:
 Originally Posted by retina It's deterministic in the same way TF is deterministic. ... You only get 53 bits to choose from. So that will hinder your ability to find factors even if you could run through all 2^53 available values.
TF is deterministic in the sense that if there's a factor in a bit level, the effort to find it in the absence of computational error is well defined. The number of sigmas prime95 supports for ECM is 253-6.
Quote:
 Step 1 took 0ms
in https://mersenneforum.org/showpost.p...5&postcount=40 is a hint not much happened there. I appreciate storm5510's questions and friendly presence, and his posts have ignited an interesting discussion in this thread, as elsewhere.

Quote:
 Originally Posted by charybdis Yes, that was the whole point of suggesting that the reader (i.e. you) run a curve at the t70 level and use that to estimate the time required for a full t70. Hint: the time for such a curve is measured in hours. Not days.
I ran a single curve at t65 level for M1619, with elapsed time ~7.3 hours on i3-370M (after searching several machines to find one with gmp-ecm installed). Step1 was 4+ hours of that. Running 1 M1277 t65 curve now.

Last fiddled with by kriesel on 2022-06-07 at 15:07

 2022-06-07, 14:56 #22 bur     Aug 2020 79*6581e-4;3*2539e-3 601 Posts As R.D. Silverman and kriesel kindly pointed out I made some annoying errors in my post above, of course not sigma has to be smooth but the group order. Thanks for the explanations, I finally understood, I think, what the probability for ECM to find a factor actually means.

 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 17:32.

Mon Dec 5 17:32:35 UTC 2022 up 109 days, 15:01, 0 users, load averages: 0.78, 0.78, 0.87