Bug in generating ECM work for small exponents

monsted · 2019-09-26, 20:52

Hi,

I was looking at doing work on small exponents and asked https://www.mersenne.org/manual_assignment/ for "ECM factoring" work on exponents between 2 and 10000. The first one generated looked fine and i started working on it. I went back to get another and it generated the same one. I then asked for ten more and it gave me two unique exponents. Finally, i asked for 50 and i got 9 unique exponents. All AIDs are unique, but the rest of the details are repeats.

Any idea what's going wrong here? I'm wondering if it just doesn't have enough unique exponents to hand out work for and it gives me duplicates instead.

I've started work on one each of the unique work units. I can clean out/unreserve the duplicates when i'm done with those.

The work i was assigned, AIDs redacted, sorted by exponent:

Code:

ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3691,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3847,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,3881,-1,110000000,11000000000,150
ECM2=X,1,2,6733,-1,110000000,11000000000,150
ECM2=X,1,2,6733,-1,110000000,11000000000,150
ECM2=X,1,2,6763,-1,110000000,11000000000,150
ECM2=X,1,2,6763,-1,110000000,11000000000,150
ECM2=X,1,2,6763,-1,110000000,11000000000,150
ECM2=X,1,2,6971,-1,110000000,11000000000,150
ECM2=X,1,2,6971,-1,110000000,11000000000,150
ECM2=X,1,2,6971,-1,110000000,11000000000,150
ECM2=X,1,2,7069,-1,110000000,11000000000,150
ECM2=X,1,2,7069,-1,110000000,11000000000,150
ECM2=X,1,2,7127,-1,110000000,11000000000,150
ECM2=X,1,2,7127,-1,110000000,11000000000,150
ECM2=X,1,2,7127,-1,110000000,11000000000,150
ECM2=X,1,2,7321,-1,110000000,11000000000,150
ECM2=X,1,2,7321,-1,110000000,11000000000,150
ECM2=X,1,2,7321,-1,110000000,11000000000,150

Syntony · 2019-09-26, 22:40

I don't think this behaviour is erroneous, although it may look a little odd on the surface. Each ECM curve is started at random coordinates and is therefore unique, so there is no duplication here. Just looking at your first exponent, 3691, the server is currently expecting to run a further 14,107 ECM curves between the bounds 110000000 and 11000000000. You've been assigned the task of running 150 curves 13 times over i.e. 1,950 curves, which is still way short of the 14,107 curves needed before the server steps up to the next higher bounds...
The server would just have looked for the most deserving candidate exponent in the range you requested until it had amassed sufficient work. The fact that it revisited some exponents just means that they were still deserving of further ECM curves despite the ones already assigned.

Tony

monsted · 2019-09-27, 00:59

Oh, that makes more sense. Doing random work seems a little odd given that we're trying to exhaustively search for things, though. Does anything prevent my 13 identical tasks from just doing the same (or at least overlapping) work?

PhilF · 2019-09-27, 01:26

Quote:

Originally Posted by monsted

Oh, that makes more sense. Doing random work seems a little odd given that we're trying to exhaustively search for things, though. Does anything prevent my 13 identical tasks from just doing the same (or at least overlapping) work?

Yes. In the worker window, you will see "s=<some very large number>" printed with each curve. That's the seed, or sigma, a random number that determines where the curve starts, and it's so large that there is practically zero mathematical chance that anyone could possibly run the exact same curve as someone else.

VBCurtis · 2019-09-27, 01:27

The seed for each individual curve is a 64 bit number. Consider the odds of 13*150 = 1950 randomly chosen 64 bit numbers repeating.

For smaller composite numbers where GMP-ECM is used (similar software, but for general use rather than the special forms Prime95 works on), the seed is a 32 bit number and still nobody worries about repeating curves. It surely happens with GMP-ECM here and there, but it's not worth worrying about.

PhilF · 2019-09-28, 02:20

I just discovered that the seed isn't so random after all.

I have 2 instances of Prime95 running ECM curves under Windows 10. I just happened to notice this correlation between them as they were running concurrently:

Instance 1 Sigma / Instance 2 Sigma

1421705357189562 / 1421703451220160
7673979774637655 / 7673977113181141
3460310890461120 / 3460311729470314
3774803163484351 / 3774800593413162

LaurV · 2019-09-28, 03:25

It may use the server time or your local tick, whatever, and for me it makes more sense to start a counter from a random point and continue from there, than generate random points every time, the "true" RNG is difficult to get anyhow and it takes time.

It is like when you buy 10 lottery tickets, if you get 10 totally random combinations, ot you just get 10 consecutive combinations, your chances to win is exactly the same, 10 in N (

we know some people who would skin us off for this affirmation

)

2019-09-28, 02:20	#6
PhilF "6800 descendent" Feb 2005 Colorado 2EB₁₆ Posts	I just discovered that the seed isn't so random after all. I have 2 instances of Prime95 running ECM curves under Windows 10. I just happened to notice this correlation between them as they were running concurrently: Instance 1 Sigma / Instance 2 Sigma 1421705357189562 / 1421703451220160 7673979774637655 / 7673977113181141 3460310890461120 / 3460311729470314 3774803163484351 / 3774800593413162 Last fiddled with by PhilF on 2019-09-28 at 02:41

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Reporting small factors to PRP doesn't work	DukeBG	FactorDB	10	2018-05-02 11:16
Exponents with only high TF work	mattmill30	PrimeNet	8	2016-08-23 18:45
P-1 on small exponents	markr	PrimeNet	18	2009-08-23 17:23
256KB L2 limited to small exponents, but 8MB L3	xorbe	Information & Answers	2	2009-02-08 05:08
Generating Small Primes	wblipp	Software	2	2005-01-05 13:29

2019-09-26, 22:40	#2
Syntony "Tony" Sep 2014 London, UK 1011100₂ Posts	I don't think this behaviour is erroneous, although it may look a little odd on the surface. Each ECM curve is started at random coordinates and is therefore unique, so there is no duplication here. Just looking at your first exponent, 3691, the server is currently expecting to run a further 14,107 ECM curves between the bounds 110000000 and 11000000000. You've been assigned the task of running 150 curves 13 times over i.e. 1,950 curves, which is still way short of the 14,107 curves needed before the server steps up to the next higher bounds... The server would just have looked for the most deserving candidate exponent in the range you requested until it had amassed sufficient work. The fact that it revisited some exponents just means that they were still deserving of further ECM curves despite the ones already assigned. Tony

2019-09-27, 00:59	#3
monsted Jan 2015 Næstved, Denmark 7₁₀ Posts	Oh, that makes more sense. Doing random work seems a little odd given that we're trying to exhaustively search for things, though. Does anything prevent my 13 identical tasks from just doing the same (or at least overlapping) work?

2019-09-27, 01:27	#5
VBCurtis "Curtis" Feb 2005 Riverside, CA 2×2,927 Posts	The seed for each individual curve is a 64 bit number. Consider the odds of 13*150 = 1950 randomly chosen 64 bit numbers repeating. For smaller composite numbers where GMP-ECM is used (similar software, but for general use rather than the special forms Prime95 works on), the seed is a 32 bit number and still nobody worries about repeating curves. It surely happens with GMP-ECM here and there, but it's not worth worrying about.

2019-09-28, 03:25	#7
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2833₁₆ Posts	It may use the server time or your local tick, whatever, and for me it makes more sense to start a counter from a random point and continue from there, than generate random points every time, the "true" RNG is difficult to get anyhow and it takes time. It is like when you buy 10 lottery tickets, if you get 10 totally random combinations, ot you just get 10 consecutive combinations, your chances to win is exactly the same, 10 in N ( we know some people who would skin us off for this affirmation )